Abhilash Nandy, Yash Agarwal, Ashish Patwa, Millon Madhur Das, Aman Bansal, Ankit Raj, Pawan Goyal, Niloy Ganguly. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

Differential Privacy (DP) has become a gold standard in privacy-preserving data analysis. While it provides a rigorous notion of privacy, there are settings where its applicability is limited. In this work, we introduce a new notion of privacy, called Utilitarian Privacy (UP), that complements DP. Informally, a UP mechanism is required not to include any “non-utile information” in the output. In particular, if two databases result in “close-by” outputs, then the mechanism should not allow distinguishing between them. On one hand UP permits weaker privacy guarantees when distinguishing between neighboring databases is important for utility; on the other hand, UP gives stronger privacy guarantees by making even non-neighboring databases indistinguishable from each other, if they yield close-by outcomes. We show that for real-valued functions, adding appropriately calibrated Laplace noise to the output, remarkably, achieves UP guarantees. A separate contribution of this work is to study private sampling, by extending the accuracy notion of mechanisms to sampling tasks. We show that for real-valued random variables, adding Laplace noise, calibrated according to a generalized sensitivity measure of the output distribution yields DP and UP. Both the above extensions build on a recently introduced notion of “lossy Wasserstein distance” - a 2-parameter error measure for distributions.

We propose a set of four novel fault-based regression test case prioritization (TCP) techniques for object-oriented programs. We seed bugs into a program to create large number of mutants. We execute each mutant with the originally designed test suite. From this, we record the number of mutants for which a test case fails. Based on this, we prioritize the test cases using four base fault-based prioritization techniques that we have proposed. Finally, we combine the results of our four base prioritizers using three ensemble methods. We have conducted experimental studies to determine the effectiveness of our proposed approaches. Our experimental results show that our proposed TCP techniques exhibit superior performance over related techniques.

Differential Privacy (DP) has become a gold standard in privacy-preserving data analysis. While it provides one of the most rigorous notions of privacy, there are many settings where its applicability is limited. Our main contribution is in augmenting differential privacy with Flexible Accuracy, which allows small distortions in the input (e.g., dropping outliers) before measuring accuracy of the output, allowing one to extend DP mechanisms to high-sensitivity functions. We present mechanisms that can help in achieving this notion for functions that had no meaningful differentially private mechanisms previously. In particular, we illustrate an application to differentially private histograms, which in turn yields mechanisms for revealing the support of a dataset or the extremal values in the data. Analyses of our constructions exploit new versatile composition theorems that facilitate modular design. All the above extensions use our new definitional framework, which is in terms of “lossy Wasserstein distance” – a 2-parameter error measure for distributions. This may be of independent interest.

Boolean Skolem function synthesis concerns syn¬thesizing outputs as Boolean functions of inputs such that a relational specification between inputs and outputs is satisfied. This problem, also known as Boolean functional synthesis, has several applications, including design of safe controllers for autonomous systems, certified QBF solving, cryptanalysis etc. Recently, complexity theoretic hardness results have been shown for the problem, although several algorithms proposed in the literature are known to work well in practice. This dichotomy between theoretical hardness and practical efficacy has motivated research on normal forms of specification representation that guarantee efficient synthesis, thus partially explaining the efficacy of some of these algorithms.In this paper we go one step further and ask if there exists a normal form representation of the specification that precisely characterizes "efficient" synthesis. We present a normal form called SAUNF that answers this question affirmatively. Specifically, a specification is polynomial time synthesizable iff it can be compiled to SAUNF in polynomial time. Additionally, a specification admits a polynomial-sized functional solution iff there exists a semantically equivalent polynomial-sized SAUNF representation. SAUNF is exponentially more succinct than well- established normal forms like BDDs and DNNFs, used in the context of AI problems, and strictly subsumes other more recently proposed forms like SynNNF. It enjoys compositional properties that are similar to those of DNNF. Thus, SAUNF provides the right trade-off in knowledge representation for Boolean functional synthesis.

In recent years, programming has witnessed a shift towards using standard libraries as a black box. However, there has not been a synchronous development of tools that can help demonstrate the working of such libraries in general programs, which poses an impediment to improved learning outcomes and makes debugging exasperating. We introduce Eye, an interactive pedagogical tool that visualizes a program's execution as it runs. It demonstrates properties and usage of data structures in a general environment, thereby helping in learning, logical debugging, and code comprehension. Eye provides a comprehensive overview at each stage during run time including the execution stack and the state of data structures. The modular implementation allows for extension to other languages and modification of the graphics as desired.

Functional languages manage heap data through garbage collection. Since static analysis of heap data is difficult, garbage collectors conservatively approximate the liveness of heap objects by reachability i.e. every object that is reachable from the root set is considered live. Consequently, a large amount of memory that is reachable but not used further during execution is left uncollected by the collector.