An official website of the United States government
Formal reasoning about hashing-based probabilistic data structures often requires reasoning about random variables where when one variable gets larger (such as the number of elements hashed into one bucket), the others tend to be smaller (like the number of elements hashed into the other buckets). This is an example ofnegative dependence, a generalization of probabilistic independence that has recently found interesting applications in algorithm design and machine learning. Despite the usefulness of negative dependence for the analyses of probabilistic data structures, existing verification methods cannot establish this property for randomized programs. To fill this gap, we design LINA, a probabilistic separation logic for reasoning about negative dependence. Following recent works on probabilistic separation logic usingseparating conjunctionto reason about the probabilistic independence of random variables, we use separating conjunction to reason about negative dependence. Our assertion logic features two separating conjunctions, one for independence and one for negative dependence. We generalize the logic of bunched implications (BI) to support multiple separating conjunctions, and provide a sound and complete proof system. Notably, the semantics for separating conjunction relies on anon-deterministic, rather than partial, operation for combining resources. By drawing on closure properties for negative dependence, our program logic supports a Frame-like rule for negative dependence andmonotoneoperations. We demonstrate how LINA can verify probabilistic properties of hash-based data structures and balls-into-bins processes.
more »
« less
Demystifying dependence
Programmers are told "depend on interfaces, not implementations." But, given a program, is it possible even to assess objectively whether such advice has been followed? Programmers frequently talk in ways like this about dependence, but the very term, like many used in software engineering, has hitherto eluded precise definition. In this work, we resolve a variety of confusions about dependence, and present a formal definition unifying multiple varieties of software dependence, grounded in Halpern and Pearl's theory of actual causation. This definition is parameterized by the formal system characterizing the property of interest, and by constraints on "reasonable changes" to the program. By picking different choices of formal system, one can specialize our definition to characterize several notions of dependence, including build, correctness, and performance dependences. Overall, our work provides a path to making conversations about software dependence fully objective, and might serve as a basis for future work that automatically checks forms of dependence that were previously too abstract or high-level to be candidates for tools.
more »
« less
- Award ID(s):
- 1801399
- PAR ID:
- 10265899
- Date Published:
- Journal Name:
- Onward! 2020: Proceedings of the 2020 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software
- Page Range / eLocation ID:
- 48 to 64
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In type systems with dependency tracking, programmers can assign an ordered set of levels to computations and prevent information flow from high-level computations to the low-level ones. The key notion in such systems isindistinguishability: a definition of program equivalence that takes into account the parts of the program that an observer may depend on. In this paper, we investigate the use of dependency tracking in the context of dependently-typed languages. We present the Dependent Calculus of Indistinguishability (DCOI), a system that adopts indistinguishability as the definition of equality used by the type checker. DCOI also internalizes that relation as an observer-indexed propositional equality type, so that programmers may reason about indistinguishability within the language. Our design generalizes and extends prior systems that combine dependency tracking with dependent types and is the first to support conversion and propositional equality at arbitrary observer levels. We have proven type soundness and noninterference theorems for DCOI and have developed a prototype implementation of its type checker.more » « less
-
Quantum computing technology may soon deliver revolutionary improvements in algorithmic performance, but it is useful only if computed answers are correct. While hardware-level decoherence errors have garnered significant attention, a less recognized obstacle to correctness is that of human programming errors—“bugs.” Techniques familiar to most programmers from the classical domain for avoiding, discovering, and diagnosing bugs do not easily transfer, at scale, to the quantum domain because of its unique characteristics. To address this problem, we have been working to adapt formal methods to quantum programming. With such methods, a programmer writes a mathematical specification alongside the program and semiautomatically proves the program correct with respect to it. The proof’s validity is automatically confirmed—certified—by a “proof assistant.” Formal methods have successfully yielded high-assurance classical software artifacts, and the underlying technology has produced certified proofs of major mathematical theorems. As a demonstration of the feasibility of applying formal methods to quantum programming, we present a formally certified end-to-end implementation of Shor’s prime factorization algorithm, developed as part of a framework for applying the certified approach to general applications. By leveraging our framework, one can significantly reduce the effects of human errors and obtain a high-assurance implementation of large-scale quantum applications in a principled way.more » « less
-
The constant-time discipline is a software-based countermeasure used for protecting high assurance cryptographic implementations against timing side-channel attacks. Constant-time is effective (it protects against many known attacks), rigorous (it can be formalized using program semantics), and amenable to automated verification. Yet, the advent of micro-architectural attacks makes constant-time as it exists today far less useful. This paper lays foundations for constant-time programming in the presence of speculative and out-of-order execution. We present an operational semantics and a formal definition of constant-time programs in this extended setting. Our semantics eschews formalization of microarchitectural features (that are instead assumed under adversary control), and yields a notion of constant-time that retains the elegance and tractability of the usual notion. We demonstrate the relevance of our semantics in two ways: First, by contrasting existing Spectre-like attacks with our definition of constant-time. Second, by implementing a static analysis tool, Pitchfork, which detects violations of our extended constant-time property in real world cryptographic libraries.more » « less
-
Given the increasing interest and need to teach students computer science in formal education settings, it is imperative to understand how to do so effectively and equitably. An important step of learning to program is being able to define the objective of a program and then plan out how to implement a program to produce the desired outcome. This step is particularly important in younger learners who may have little experience with programming or trying to create their own technological artifacts. In this paper, we explore how to scaffold young programmers in planning their open-ended programs as part of an intermediate Scratch curriculum for middle grade students. We analyze 203 paper and virtual planning documents from 103 5th-8th grade students. Our results reveal that the students often completed a majority of the document, which was consistent across grade levels. However, we found differences in student completion based on teacher and between physical and virtual documents. This work advances our understanding of how to support novice, young programmers in planning programs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3426428.3426916
