Search papers, labs, and topics across Lattice.
This paper introduces a framework using epistemic logic to analyze information leakage in concurrent object implementations, contrasting the knowledge available under abstract specifications with that of concrete implementations. The authors establish several non-leaking implementation models, presenting fully-non-leaking wait-free implementations for multi-valued registers and bounded max registers, while revealing that a fully-non-leaking unbounded max register cannot be achieved wait-free from finite-state objects. Their findings highlight that while non-leakage can often coexist with correctness and progress, significant limitations exist in certain scenarios.
Fully-non-leaking wait-free implementations are possible for some concurrent objects, but not all鈥攔evealing critical limitations in information security for concurrent systems.
Abstract specifications of concurrent objects determine which values operations may return, but they also implicitly constrain which information operations may know, for example the arguments of other operations that do not affect their outcome, or even whether such operations occurred. Concrete implementations, while correct with respect to the abstract specification, may nonetheless expose additional information through their internal coordination mechanisms. We introduce a framework for reasoning about information leakage in concurrent implementations. The framework uses epistemic logic to compare what a process may know under an abstract specification with what it may know in a concrete implementation, using the abstract object itself as the reference for permissible observations. This yields several notions of non-leaking implementations. Using this framework, we investigate both the possibilities and limitations of non-leaking implementations. We present fully-non-leaking wait-free implementations of multi-valued registers and bounded max registers, but show that a fully-non-leaking unbounded max register cannot be implemented in a wait-free manner from finite-state base objects. We then consider a weaker guarantee, obtaining argument-non-leaking implementations of stacks, queues, and approximate agreement. These results demonstrate that non-leakage guarantees are often compatible with correctness and progress requirements, while also indicating their limitations.
