Browsing by Subject "Transactions"
Now showing 1 - 4 of 4
- Results Per Page
- Sort Options
Item Letter to H.B. Stenzel from W.A. Petersen on 1954-03-04(1954-03-04) Petersen, W.A.Item Operating system transactions(2010-12) Porter, Donald E.; Witchel, Emmett; Alvisi, Lorenzo; McKinley, Kathryn S.; Shmatikov, Vitaly; Swift, MichaelApplications must be able to synchronize accesses to operating system (OS) resources in order to ensure correctness in the face of concurrency and system failures. This thesis proposes system transactions, with which the programmer specifies atomic updates to heterogeneous system resources and the OS guarantees atomicity, consistency, isolation, and durability (ACID). This thesis provides a model for system transactions as a concurrency control mechanism. System transactions efficiently and cleanly solve long-standing concurrency problems that are difficult to address with other techniques. For example, malicious users can exploit race conditions between distinct system calls in privileged applications, gaining administrative access to a system. Programmers can eliminate these vulnerabilities by eliminating these race conditions with system transactions. Similarly, failed software installations can leave a system unusable. System transactions can roll back an unsuccessful software installation without disturbing concurrent, independent updates to the file system. This thesis describes the design and implementation of TxOS, a variant of Linux 2.6.22 that implements system transactions. The thesis contributes new implementation techniques that yield fast, serializable transactions with strong isolation and fairness between system transactions and non-transactional activity. Using system transactions, programmers can build applications with better performance or stronger correctness guarantees from simpler code. For instance, wrapping an installation of OpenSSH in a system transaction guarantees that a failed installation will be rolled back completely. These atomicity properties are provided by the OS, requiring no modification to the installer itself and adding only 10% performance overhead. The prototype implementation of system transactions also minimizes non-transactional overheads. For instance, a non-transactional compilation of Linux incurs negligible (less than 2%) overhead on TxOS. Finally, this thesis describes a new lock-free linked list algorithm, called OLF, for optimistic, lock-free lists. OLF addresses key limitations of prior algorithms, which sacrifice functionality for performance. Prior lock-free list algorithms can safely insert or delete a single item, but cannot atomically compose multiple operations (e.g., atomically move an item between two lists). OLF provides both arbitrary composition of list operations as well as performance scalability close to previous lock-free list designs. OLF also removes previous requirements for dynamic memory allocation and garbage collection of list nodes, making it suitable for low-level system software, such as the Linux kernel. We replace lists in the Linux kernel's directory cache with OLF lists, which currently requires a coarse-grained lock to ensure invariants across multiple lists. OLF lists in the Linux kernel improve performance of a filesystem metadata microbenchmark by 3x over unmodified Linux at 8 CPUs. The TxOS prototype demonstrates that a mature OS running on commodity hardware can provide system transactions at a reasonable performance cost. As a practical OS abstraction for application developers, system transactions facilitate writing correct application code in the presence of concurrency and system failures. The OLF algorithm demonstrates that application developers can have both the functionality of locks and the performance scalability of a lock-free linked list.Item Orchestration and atomicity(2013-08) Kitchin, David Wilson; Misra, Jayadev; Cook, William RandallThis dissertation presents the concurrent programming language Ora, an extension of the Orc orchestration language with the capability to execute transactions. A new formal definition of transactions is given, in terms of two complementary properties: atomicity and coatomicity. These properties are described in terms of a partial order of events, rather than as properties of a totally ordered program trace. Atomicity and coatomicity are ensured in Ora programs by a novel algorithm for multiversion concurrency control.Item Secure protocols for contactless credit cards and electronic wallets(2017-05) Jensen, Oliver Christopher; Gouda, Mohamed G., 1947-; Alvisi, Lorenzo; Qiu, Lili; Garg, Vijay KThe contactless credit card protocol in use today is insecure. The credit card industry has chosen to use the NFC channel for contactless transactions. However, reliance on NFC's short range has led to poor assumptions in the contactless credit card protocol. For example, the card assumes (sometimes incorrectly) that its ability to receive a solicitation implies the cardholder's intent to purchase. In this dissertation, we examine the protocol currently in use, and present a family of three replacement protocols to defend against its deficiencies. First, we consider "outsider" attacks (e.g. eavesdropping, skimming attacks, relay attacks, and attacks facilitated by compromised points of sale) and design our first protocol to defend against these attacks. We call this protocol the Externally Secure CC Protocol, and design it using stepwise refinement. This protocol makes use of single-use "charge tokens" verifiable by the bank, while minimizing computation that needs to occur on the card. Second, we identify two attacks which may be carried out by malicious retailers: Over-charge attacks and Transparent Bridge attacks. Both attacks are predicated on the customer's lack of participation in the protocol, and involve modifying or replacing a charge after it has been confirmed by the customer. We look to Electronic Wallet applications (such as Android Pay and Apple Wallet), which provide a channel between customer and card. We augment the Externally Secure CC Protocol using this channel to construct the Secure CC Protocol, binding charge tokens to a given price, and thus stymieing both outsider and malicious retailer attacks. The Secure CC Protocol supports a property known as linkability: while only the bank can verify charge tokens, tokens from the same card can be recognized as such by the retailer. This property is also supported by the (insecure) protocol in use today, and is commonly used by retailers to construct marketing profiles on their customers. However, linkability has serious consumer privacy consequences, so we consider the converse property of unlinkability, where a retailer cannot identify different purchases as having been made by the same card. We require that our unlinkable protocol make use of existing infrastructure, so as not to require retailer cooperation. In response, we design the Unlinkable Wallet Protocol, leveraging techniques from the Secure CC Protocol to guard against malicious outsiders and retailers, while tunneling secure and unlinkable charge tokens through the protocol in use today.