- talks - lists.cs.princeton.edu

Abhinav Narain (Georgia Institute of Technology) will present "Near-Field Deniable Communication" on Wednesday, May 24, 2017 in the CITP conference room, 3rd Fl, Sherrerd Hall at 11am
by Nicki Gotsis 24 May '17

24 May '17

Abhinav Narain (Georgia Institute of Technology) will present his defense talk "Near-Field Deniable Communication" on Wednesday, May 24, 2017 in the CITP conference room, 3rd Fl, Sherrerd Hall at 11am (Webcast : http://bit.ly/2qFJXx6) Title: Near-Field Deniable Communication ----- Abhinav Narain School of Computer Science College of Computing Georgia Institute of Technology Committee --------- Prof. Nick Feamster (Adviser, School of Computer Science, Princeton University) Prof. Mostafa Ammar, (School of Computer Science, Georgia Institute of Technology) Prof. Taesoo Kim, (School of Computer Science, Georgia Institute of Technology) Prof. Alex Snoeren, (Dept. of Computer Science, University of California, San Diego) Date: Wednesday, May 24, 2017 Time: 11 am to 1 pm EST Location: CITP conference room, third floor, Sherrerd Hall, Princeton University Webcast : http://bit.ly/2qFJXx6 There is constant surveillance by employers, corporations, and governments. Long people have wanted to keep their communication private but With increasing interest of state and private organizations and corporations in the daily lives of people, such a discussion is on the rise. This dissertation develops techniques and systems that empower users to evade such intentions of adversaries. Our work builds from the observation to leverage randomness in physical nature of the world everywhere, specifically using technologies such as wireless and power-lines networks in urban settings. This thesis is divided into two parts. First part, we develop Denali, which allows deniable communication in wireless 802.11 networks. Denali achieves this by leveraging the weakness of wireless networks which has packet corruption due to its ubiquitous nature of being broadcast medium. This is the first such system which uses off-the-shelf commodity hardware to users. In the second part, we explore a different network primarily used for powering devices in building infrastructure -- power-line network. We build Power-line Whisperer, a physical layer covert communication channel. Power-line Whisperer is the first of its kind of system to make it easier for people to to do deniable communication on power-line networks. Both these systems allow the users to do point-to-point communication and defend against powerful adversaries who might be interested in snooping on the message exchange for malicious reasons.

1 1

Yonatan Naaman will present his Pre FPO "Hardness from Dense Subgraph Conjectures" on Thursday, May 25th, 2017 in CS 402 at 6pm.
by Nicki Gotsis 22 May '17

22 May '17

Yonatan Naaman will present his Pre FPO "Hardness from Dense Subgraph Conjectures" on Thursday, May 25th, 2017 in CS 402 at 6pm. Everyone is invited to attend his talk. The members of his committee are as follows: Moses Charikar (adviser) Sanjeev Arora (reader) Anthony Wirth (U. Melbourne) (reader) Mark Braverman (non-reader) Matt Weinberg (non-reader) Title: "Hardness from Dense Subgraph Conjectures". Abstract: Karp's seminal paper on NP-Completeness provided computer scientists with a toolkit for showing computational hardness, conditioned on a complexity theoretic conjecture, for a wide variety of optimization problems. However, the techniques used in his paper say little about the hardness of approximating the optimal objective values of these problems. While researchers have since managed to find tight bounds on the approximability of some of these NP-hard problems, many others still have embarrassingly large gaps between their known upper and lower limits of approximation. To fill in these gaps, researchers have posed myriad new complexity theoretic conjectures that entail stronger lower bounds at the expense of more demanding hypotheticals. One class of conjectures focuses on the approximability of the Densest k-Subgraph (DkS) problem. Namely, the conjectured hardness of both adversarial and average-case variants of DkS has been shown to imply stronger hardness for many problems for which good approximation algorithms have proven elusive. In this thesis, we describe techniques for proving stronger hardness results conditioned on both the known and the conjectured hardness of Densest k-Subgraph. We show how previous results on DkS imply stronger lower bounds on ``MinRep-hard'' problems, as well as a simple technique for converting many proofs of MinRep-hardness into proofs of DkS-hardness. Using this and other techniques, we show DkS hardness for problems such as Minimum Colored Cut, Target Set Selection, Minimum Monotone Satisfying Assignment (MMSA), Network Flow Interdiction, Power Dominating Set, Densest k-Common Subgraph, among others. In the case of Target Set Selection and MMSA, we show how to obtain substantially stronger lower bounds by exploiting the self-similar structure of instances conjectured to be average-case-hard. We also provide improved approximation algorithms for some of the discussed problems.

1 0

Niranjani Prasad will present her generals exam Thursday, May 25, 2017 at 10am in CS 401 [updated]
by Nicki Gotsis 22 May '17

22 May '17

Niranjani Prasad will present her generals exam Thursday, May 25 , 2017 at 10am in CS 401. The members of her committee are: Barbara Engelhardt (adviser), Warren Powell, and Sebastian Seung. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Title: A Reinforcement Learning Approach to Intervention Protocols in the ICU Abstract: The management of routine interventions such as mechanical ventilation and sedation, blood transfusions, or the administration of fluids and vasopressors, constitute a major part of the care of patients in intensive care units (ICUs). Timely and proportionate interventions are crucial to improving patient outcomes and reducing hospital costs, but the effect of these procedures are often poorly understood—particularly when handling heterogenous patient populations—and clinical opinion on best protocols vary. In this work, we focus on the development of decision support for weaning from mechanical ventilation, that leverages available information in the data-intensive ICU setting to predict time to extubation readiness, and recommend a personalized regime of sedation and ventilator support. To this end, we employ off-policy reinforcement learning algorithms to learn an optimal sequence of treatment actions from sub-optimal historical ICU data. We model patient admissions as Markov decision processes, developing tailored representations of the problem state, action space and reward function, and learn treatment policies using Fitted Q-iteration with tree-based regressors and with feedforward neural networks. We demonstrate that this framework shows promise in recommending intervention protocols with improved outcomes, on average outperforming clinical practice in controlling physiological stability and reintubation rates. Reading List: Textbook: Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction . Vol. 1. No. 1. Cambridge: MIT press, 1998. Papers: Ernst, Damien, Pierre Geurts, and Louis Wehenkel. " Tree-based batch mode reinforcement learning ." Journal of Machine Learning Research 6, 2005. Riedmiller, Martin. " Neural fitted Q iteration–first experiences with a data efficient neural reinforcement learning method ." European Conference on Machine Learning. Springer Berlin Heidelberg, 2005. Mnih, Volodymyr, et al. " Human-level control through deep reinforcement learning. ” Nature, 2014. Rasmussen, Carl Edward, and Malte Kuss. " Gaussian Processes in Reinforcement Learning ." NIPS. Vol. 4. 2003. Abbeel, Pieter, and Andrew Y. Ng. " Apprenticeship learning via inverse reinforcement learning ." Proceedings of the twenty-first international conference on Machine learning. ACM, 2004. Escandell-Montero, Pablo, et al. " Optimization of anemia treatment in hemodialysis patients via reinforcement learning ." Artificial intelligence in medicine 62.1, 2014. Guez, Arthur, et al. " Adaptive Treatment of Epilepsy via Batch-mode Reinforcement Learning ." AAAI. 2008. Ernst, Damien, et al. " Clinical data based optimal STI strategies for HIV: a reinforcement learning approach. " Decision and Control, 2006 45th IEEE Conference on. IEEE, 2006. Nemati, Shamim, Mohammad M. Ghassemi, and Gari D. Clifford. " Optimal medication dosing from suboptimal clinical examples: A deep reinforcement learning approach. " Engineering in Medicine and Biology Society (EMBC), IEEE, 2016. Wu, Mike, et al. " Understanding vasopressor intervention and weaning: Risk prediction in a public heterogeneous clinical time series database ." Journal of the American Medical Informatics Association, 2016.

1 0

Colloquium Speaker: Manfred K. Warmuth, Today- 12:30pm
by Nicole E. Wagenblast 22 May '17

22 May '17

Colloquium Speaker Manfred K Warmuth, University of California, Santa Cruz Monday, May 22, 12:30pm Computer Science 105 The blessing and the curse of the multiplicative updates - discusses connections between in evolution and the multiplicative updates of online learning Multiplicative updates multiply the parameters by nonnegative factors. These updates are motivated by a Maximum Entropy Principle and they are prevalent in evolutionary processes where the parameters are for example concentrations of species and the factors are survival rates. The simplest such update is Bayes rule and we give an in vitro selection algorithm for RNA strands that implements this rule in the test tube where each RNA strand represents a different model. In one liter of the RNA soup there are approximately 10^15 different strands and therefore this is a rather high-dimensional implementation of Bayes rule. We investigate multiplicative updates for the purpose of learning online while processing a stream of examples. The ``blessing'' of these updates is that they learn very fast in the short term because the good parameters grow exponentially. However their ``curse'' is that they learn too fast and wipe out parameters too quickly. This can have a negative effect in the long term. We describe a number of methods developed in the realm of online learning that ameliorate the curse of the multiplicative updates. The methods make the algorithm robust against data that changes over time and prevent the currently good parameters from taking over. We also discuss how the curse is circumvented by nature. Surprisingly, some of nature's methods parallel the ones developed in Machine Learning, but nature also has some additional tricks. This will be a high level talk. No background in online learning will be required. We will give a number of open problems and discuss how these updates are applied for training feed forward neural nets.

1 0

Colloquium Speaker: Manfred K. Warmuth, Monday May 22- 12:30pm - reminder
by Nicole E. Wagenblast 21 May '17

21 May '17

Colloquium Speaker Manfred K Warmuth, University of California, Santa Cruz Monday, May 22, 12:30pm Computer Science 105 The blessing and the curse of the multiplicative updates - discusses connections between in evolution and the multiplicative updates of online learning Multiplicative updates multiply the parameters by nonnegative factors. These updates are motivated by a Maximum Entropy Principle and they are prevalent in evolutionary processes where the parameters are for example concentrations of species and the factors are survival rates. The simplest such update is Bayes rule and we give an in vitro selection algorithm for RNA strands that implements this rule in the test tube where each RNA strand represents a different model. In one liter of the RNA soup there are approximately 10^15 different strands and therefore this is a rather high-dimensional implementation of Bayes rule. We investigate multiplicative updates for the purpose of learning online while processing a stream of examples. The ``blessing'' of these updates is that they learn very fast in the short term because the good parameters grow exponentially. However their ``curse'' is that they learn too fast and wipe out parameters too quickly. This can have a negative effect in the long term. We describe a number of methods developed in the realm of online learning that ameliorate the curse of the multiplicative updates. The methods make the algorithm robust against data that changes over time and prevent the currently good parameters from taking over. We also discuss how the curse is circumvented by nature. Surprisingly, some of nature's methods parallel the ones developed in Machine Learning, but nature also has some additional tricks. This will be a high level talk. No background in online learning will be required. We will give a number of open problems and discuss how these updates are applied for training feed forward neural nets.

1 0

Niranjani Prasad will present her generals exam Thursday, May 25, 2017 at 10am in CS 401.
by Nicki Gotsis 18 May '17

18 May '17

Niranjani Prasad will present her generals exam Thursday, May 25, 2017 at 10am in CS 401. The members of her committee are: Barbara Engelhardt (adviser), Warren Powell, and Sebastian Seung. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Title: A Reinforcement Learning Approach to Intervention Protocols in the ICU Abstract: The management of routine interventions such as mechanical ventilation and sedation, blood transfusions, or the administration of fluids and vasopressors, constitute a major part of the care of patients in intensive care units (ICUs). Timely and proportionate interventions are crucial to improving patient outcomes and reducing hospital costs, but the effect of these procedures are often poorly understood—particularly when handling heterogenous patient populations—and clinical opinion on best protocols vary. In this work, we focus on the development of decision support for weaning from mechanical ventilation, that leverages available information in the data-intensive ICU setting to predict time to extubation readiness, and recommend a personalized regime of sedation and ventilator support. To this end, we employ off-policy reinforcement learning algorithms to learn an optimal sequence of treatment actions from sub-optimal historical ICU data. We model patient admissions as Markov decision processes, developing tailored representations of the problem state, action space and reward function, and learn treatment policies using Fitted Q-iteration with tree-based regressors and with feedforward neural networks. We demonstrate that this framework shows promised in recommending intervention protocols with improved outcomes, on average outperforming clinical practice in controlling physiological stability and reintubation rates. Reading List: Textbook: Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction . Vol. 1. No. 1. Cambridge: MIT press, 1998. Papers: Ernst, Damien, Pierre Geurts, and Louis Wehenkel. " Tree-based batch mode reinforcement learning ." Journal of Machine Learning Research 6, 2005. Riedmiller, Martin. " Neural fitted Q iteration–first experiences with a data efficient neural reinforcement learning method. " European Conference on Machine Learning. Springer Berlin Heidelberg, 2005. Mnih, Volodymyr, et al. " Human-level control through deep reinforcement learning ." Nature 518.7540, 2015 . Rasmussen, Carl Edward, and Malte Kuss. " Gaussian Processes in Reinforcement Learning ." NIPS. Vol. 4. 2003. Abbeel, Pieter, and Andrew Y. Ng. " Apprenticeship learning via inverse reinforcement learning ." Proceedings of the twenty-first international conference on Machine learning. ACM, 2004. Escandell-Montero, Pablo, et al. " Optimization of anemia treatment in hemodialysis patients via reinforcement learning ." Artificial intelligence in medicine 62.1, 2014. Guez, Arthur, et al. " Adaptive Treatment of Epilepsy via Batch-mode Reinforcement Learning ." AAAI. 2008. Ernst, Damien, et al. " Clinical data based optimal STI strategies for HIV: a reinforcement learning approach ." Decision and Control, 2006 45th IEEE Conference on. IEEE, 2006. Nemati, Shamim, Mohammad M. Ghassemi, and Gari D. Clifford. " Optimal medication dosing from suboptimal clinical examples: A deep reinforcement learning approach ." Engineering in Medicine and Biology Society (EMBC), IEEE, 2016. Wang, Yingfei, and Warren Powell. " An optimal learning method for developing personalized treatment regimes. " arXiv preprint arXiv: 1607.01462 2016 . Padmanabhan, Regina, Nader Meskin, and Wassim M. Haddad. " Closed-loop control of anesthesia and mean arterial pressure using reinforcement learning ." Biomedical Signal Processing and Control 22, 2015. Wu, Mike, et al. " Understanding vasopressor intervention and weaning: Risk prediction in a public heterogeneous clinical time series database ." Journal of the American Medical Informatics Association, 2016.

1 0

Colloquium Speaker: Manfred K. Warmuth, Monday May 22- 12:30pm
by Nicole E. Wagenblast 18 May '17

18 May '17

Colloquium Speaker Manfred K Warmuth, University of California, Santa Cruz Monday, May 22, 12:30pm Computer Science 105 The blessing and the curse of the multiplicative updates - discusses connections between in evolution and the multiplicative updates of online learning Multiplicative updates multiply the parameters by nonnegative factors. These updates are motivated by a Maximum Entropy Principle and they are prevalent in evolutionary processes where the parameters are for example concentrations of species and the factors are survival rates. The simplest such update is Bayes rule and we give an in vitro selection algorithm for RNA strands that implements this rule in the test tube where each RNA strand represents a different model. In one liter of the RNA soup there are approximately 10^15 different strands and therefore this is a rather high-dimensional implementation of Bayes rule. We investigate multiplicative updates for the purpose of learning online while processing a stream of examples. The ``blessing'' of these updates is that they learn very fast in the short term because the good parameters grow exponentially. However their ``curse'' is that they learn too fast and wipe out parameters too quickly. This can have a negative effect in the long term. We describe a number of methods developed in the realm of online learning that ameliorate the curse of the multiplicative updates. The methods make the algorithm robust against data that changes over time and prevent the currently good parameters from taking over. We also discuss how the curse is circumvented by nature. Surprisingly, some of nature's methods parallel the ones developed in Machine Learning, but nature also has some additional tricks. This will be a high level talk. No background in online learning will be required. We will give a number of open problems and discuss how these updates are applied for training feed forward neural nets.

1 0

Cyril Zhang will present his generals exam Thursday, May 25, 2017 at 3pm in CS 402
by Nicki Gotsis 18 May '17

18 May '17

Cyril Zhang will present his generals exam Thursday, May 25, 2017 at 3pm in CS 402 The members of his committee are: Elad Hazan (adviser), Sanjeev Arora, and Matt Weinberg Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Topic: Two Views of Non-Convex Regret Minimization Abstract: I will discuss the problem of efficient online regret minimization with non-convex loss functions. Two distinct (yet pleasingly nebulously connected) approaches are considered; both results are j oint work with Karan Singh and Prof. Elad Hazan. In the first part of my talk, I will present a new framework for general online non-convex optimization (ONCO). I will introduce the desiderata of such a framework, showing how we must avert issues of computational intractability by defining a suitable notion of regret. I will introduce our time-smoothed regret measure, and justify it with tight upper and lower bounds, along with reductions to the full-information and stochastic offline cases. Finally, I will show some extensions and applications. Primarily, our framework gives rise to a new solution concept in repeated games; I will discuss some natural settings in which our algorithms are practical and give provable guarantees for learning in games. In the second part, I will present a second approach, in which one leverages the structure of an ONCO problem to make it amenable to the tools of online convex optimization (OCO). We consider the non-convex problem of maximum-likelihood online prediction of linear dynamical systems (LDS). Relying upon the spectral theory of Hankel matrices, we formulate an approximate convex relaxation to this problem. This results in a black-box reduction to OCO, from which we derive a simple, practical method for predicting sequences arising from an LDS. Books: - Introduction to Online Convex Optimization. Elad Hazan. - Understanding Machine Learning. Shai Shalev-Shwartz and Shai Ben-David. Papers: - Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming. Saeed Ghadimi and Guanghui Lan. - Cubic regularization of Newton method and its global performance. Yurii Nesterov and B.T. Polyak. - The Multiplicative Weights Update Method: A Meta-Algorithm and Applications. Sanjeev Arora, Elad Hazan, Satyen Kale. - Online Convex Programming and Generalized Infinitesimal Gradient Ascent. Martin Zinkevich. - Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. John Duchi, Elad Hazan, and Yoram Singer. - Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. Rie Johnson and Tong Zhang. - Efficient algorithms for online decision problems. Adam Kalai and Santosh Vempala. - Online Linear Optimization via Smoothing. Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. - Matrix Completion has No Spurious Local Minimum. Rong Ge, Jason D. Lee, and Tengyu Ma. - Gradient Descent Learns Linear Dynamical Systems. Moritz Hardt, Tengyu Ma, and Benjamin Recht.

1 0

Ariel Schvartzman Cohenca will present his generals exam Thursday, May 25, 2017 at 1pm in CS 401.
by Nicki Gotsis 18 May '17

18 May '17

Ariel Schvartzman Cohenca will present his generals exam Thursday, May 25, 2017 at 1pm in CS 401. The members of his committee are: Matt Weinberg (adviser), Gillat Kol, and Zeev Dvir. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. While Nash equilibria are arguably the most studied notion of equilibrium in strategic games, recent results regarding their communication and computational complexity have undermined their prevalence as a predictable solution concept when agents are computationally bounded. In particular, results show that two players cannot converge to any approximate Nash equilibria in the limited communication setting where each player only knows its utility function. For the case of 2-player games, it has been recently shown that even computing approximate Nash equilibria requires poly(n) bits of communication[BR16]. In addition even in the setting where all the payoffs matrices are known Nash equilibria seem to be unnatural due to their computational hardness. Computing any exact Nash equilibrium is known to be PPAD-complete, making it unlikely to have any polynomial time algorithm [CDT09, Daskalakis2009]. Furthermore, it has been shown that under the Exponential Time Hypothesis (ETH) for the class PPAD, eps-approximate Nash equilibria cannot be computed in time faster than quasi-polynomial in the number of strategies per player[Rubinstein16a]. This almost exactly matches the algorithm of [LMM03]. These results suggest that approximate Nash equilibria may not be efficiently computable. Correlated equilibria arise as an alternative equilibrium concept. This notion, introduced in the seminal work of [Aumann74], allows agents to cooperate in order to reach stability. Informally, a strategy profile is a correlated equilibrium when a referee or trusted party can draw strategy samples according to it and recommend them to the players in such a way that they have no incentive to consistently deviate, assuming everyone else plays according to their recommendation. Computationally, correlated equilibria are in sharp contrast to Nash equilibria: there exists an ellipsoid-based algorithm to compute exact correlated equilibrium polynomial time even for multi-player games for a large (but not universal) class of games including graphical games, anonymous games, congestion games and scheduling games[PR2008]. Unfortunately this result is still unsettling: one can imagine many settings where a referee may not have access to all utility functions or where players may not want to share such information with a referee. With this in consideration it becomes more natural to ask whether there is an efficient communication protocol for computing approximate correlated equilibria better than the naive one where each player sends their payoff matrix to a referee who computes the answer. Given recent developments, this is the next fundamental problem between communication complexity and algorithmic game theory that needs to be addressed, both in terms of communication and query complexity. In this work we address the question posed by [BR16] of providing lower bounds for the communication complexity of approximate correlated equilibrium in 2-player games. The arguments used on the lower bound proof rely on tools from information theory, which lower bounds communication cost. While this talk focuses on a single result, my research interests lie in understanding the complexity of approximate solution concepts. There are different lenses through which we analyze problems when studying equilibria: computation, communication, query (amongst others). Other similar projects I have worked on involve bounds for the menu complexity of optimal and approximate mechanism design and understanding the efficiency loss of ‘simple auctions’ when compared to their optimal counterparts in specific settings. Joint work with Young Kun Ko. Reading list: - Algorithmic Game Theory. E. Tardos, T. Roughgarden, V. Vazirani, N. Nisan. 2007. - 20 Lectures in Algorithmic Game Theory. T. Roughgarden. 2016. Papers: - Settling the complexity of computing approximate two-player Nash equilibria. A. Rubinstein. 2016. - Inapproximability of Nash Equilibrium. A. Rubinstein. 2015. - Adaptive procedure, correlated equilibrium, no regret, regret-matching, simple strategies. S. Hart, A. Mas-Collel. 2000. - Communication complexity of approximate Nash equilibria. Y. Babichenko, A. Rubinstein. 2016. - Playing Large Games Using Simple Strategies. R. Lipton, E. Markakis, A. Mehta. 2003 - How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. S. Hart, Y. Mansour. 2010. - The communication complexity of uncoupled nash equilibrium procedures. S. Hart, Y. Mansour. 2007. - The complexity of computing a Nash equilibrium. C. Daskalakis, A. Goldberg, C. Papadimitriou. 2008. - Settling the Complexity of Computing Two-player Nash Equilibria. X. Chen, X. Deng, S. Teng. 2009. - Computing Equilibria: A Computational Complexity Perspective. T. Roughgarden. 2010. - Communication Complexity (for Algorithm Designers), Chapter 7: Lower Bounds in Algorithmic Game Theory. 2016. - Communication Complexity as a Lower Bound for Learning in Games. V. Connitzer, T. Sandholm. 2004.

1 0

Sotirios Apostolakis will present his general exam on Wednesday, May 24, 2017 at 3pm in CS 401.
by Nicki Gotsis 17 May '17

17 May '17

Sotirios Apostolakis will present his general exam on Wednesday, May 24, 2017 at 3pm in CS 401. The members of his committee are: David August (adviser), Nick Feamster, and Andrew Appel. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Enabling Practical Full System Containment Abstract: Acknowledging that modern computing systems are too complex to be vulnerability free, we advocate for a single, simple component that would quarantine the ill effects of compromised system components. Work on a system called TrustGuard has shown that it is feasible for a simple and pluggable hardware element, called the Sentry, to offer containment of untrusted hardware, by ensuring that the system only outputs results of correct execution of signed programs. TrustGuard’s original focus was to protect against hardware vulnerabilities and signed programs needed to be entirely trusted. This work extends TrustGuard’s checking scheme with a new programming model. This new model exposes the Sentry to programmers by allowing them to reduce the amount of code that is trusted and checked by the Sentry. We implemented a library for runtime integrity checking of key-value database operations to demonstrate the practicality of the enhanced checking scheme and exemplify how Sentry produces trusted output using untrusted applications, OS and hardware. Reading list: Books: * Andrew W. Appel, Modern Compiler Implementation in ML. Cambridge University Press, 1998 * Ross J. Anderson. 2008. Security Engineering: A Guide to Building Dependable Distributed Systems (2 ed.). Wiley Publishing. (Chapters 3,4,5,11,16) * John L. Hennessy and David A. Patterson. 2011. Computer Architecture, Fifth Edition: A Quantitative Approach (5th ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA Papers: * Riad S. Wahby, Max Howald, Siddharth J. Garg, Abhi Shelat, and Michael Walfish. Verifiable ASICs. In IEEE S&P 2016. * Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath Setty, Andrew J. Blumberg, and Michael Walfish. 2013. Verifying computations with state. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). * G.E. Suh, D Clarke, B. Gassend, M. van Dijk, S. Devadas. AEGIS: architecture for tamper-evident and tamper-resistant processing. In Proceedings of the 17th annual international conference on Supercomputing, ICS’03 * T. M. Austin, "DIVA: a reliable substrate for deep submicron microarchitecture design," Microarchitecture, 1999. MICRO-32. Proceedings. 32nd Annual International Symposium on, Haifa, 1999 * A. Miller, M. Hicks, J. Katz, and E. Shi. Authenticated data structures, generically. In POPL 2014. * Goodrich, Michael T., Roberto Tamassia, and Andrew Schwerin. "Implementation of an authenticated dictionary with skip lists and commutative hashing." DISCEX'01, 2001. * Premkumar T. Devanbu, Michael Gertz, Charles U. Martel, and Stuart G. Stubblebine. Authentic third-party data publication. In DBSec, volume 201 of IFIP Conference Proceedings, 2000. * B. Rogers, S. Chhabra, M. Prvulovic and Y. Solihin, "Using Address Independent Seed Encryption and Bonsai Merkle Trees to Make Secure Processors OS- and Performance-Friendly”, MICRO 2007.

1 0