Shaobo He
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Shaobo He has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
Zvonimir Rakamarić
University of Utah
4 shared publications- Aaron Eline
Amazon Web Services, Arlington, United States
2 shared publications - Andrew M. Wells
Amazon Web Services, Santa Clara, United States
2 shared publications - Anwar Mamat
University of Maryland, College Park, USA
2 shared publications - Craig Disselkoen
Amazon Web Services, Arlington, United States
2 shared publications - Emina Torlak
Amazon Web Services, Seattle, United States
2 shared publications
Latest Publications
- Open Access
- 10 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 351-357
How We Built Cedar: A Verification-Guided Approach
This paper presents verification-guided development (VGD), a software engineering process we used to build Cedar, a new policy language for expressive, fast, safe, and analyzable authorization. Developing a system with VGD involves writing an executable model of the system and mechanically proving properties about the model; writing production code for the system and using differential random testing (DRT) to check that the production code matches the model; and using property-based testing (PBT) to check properties of unmodeled parts of the production code. Using VGD for Cedar, we can build fast, idiomatic production code, prove our model correct, and find and fix subtle implementation bugs that evade code reviews and unit testing. While carrying out proofs, we found and fixed 4 bugs in Cedar’s policy validator, and DRT and PBT helped us find and fix 21 additional bugs in various parts of Cedar.
- 10 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 351-357
Open AccessHow We Built Cedar: A Verification-Guided Approach
This paper presents verification-guided development (VGD), a software engineering process we used to build Cedar, a new policy language for expressive, fast, safe, and analyzable authorization. Developing a system with VGD involves writing an executable model of the system and mechanically proving properties about the model; writing production code for the system and using differential random testing (DRT) to check that the production code matches the model; and using property-based testing (PBT) to check properties of unmodeled parts of the production code. Using VGD for Cedar, we can build fast, idiomatic production code, prove our model correct, and find and fix subtle implementation bugs that evade code reviews and unit testing. While carrying out proofs, we found and fixed 4 bugs in Cedar’s policy validator, and DRT and PBT helped us find and fix 21 additional bugs in various parts of Cedar.
- Open Access
- 29 April 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (OOPSLA1) , 670-697
Cedar: A New Language for Expressive, Fast, Safe, and Analyzable Authorization
Cedar is a new authorization policy language designed to be ergonomic, fast, safe, and analyzable. Rather than embed authorization logic in an application’s code, developers can write that logic as Cedar policies and delegate access decisions to Cedar’s evaluation engine. Cedar’s simple and intuitive syntax supports common authorization use-cases with readable policies, naturally leveraging concepts from role-based, attribute-based, and relation-based access control models. Cedar’s policy structure enables access requests to be decided quickly. Cedar’s policy validator leverages optional typing to help policy writers avoid mistakes, but not get in their way. Cedar’s design has been finely balanced to allow for a sound and complete logical encoding, which enables precise policy analysis, e.g., to ensure that when refactoring a set of policies, the authorized permissions do not change. We have modeled Cedar in the Lean programming language, and used Lean’s proof assistant to prove important properties of Cedar’s design. We have implemented Cedar in Rust, and released it open-source. Comparing Cedar to two open-source languages, OpenFGA and Rego, we find (subjectively) that Cedar has equally or more readable policies, but (objectively) performs far better.
- 29 April 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (OOPSLA1) , 670-697
Open AccessCedar: A New Language for Expressive, Fast, Safe, and Analyzable Authorization
Cedar is a new authorization policy language designed to be ergonomic, fast, safe, and analyzable. Rather than embed authorization logic in an application’s code, developers can write that logic as Cedar policies and delegate access decisions to Cedar’s evaluation engine. Cedar’s simple and intuitive syntax supports common authorization use-cases with readable policies, naturally leveraging concepts from role-based, attribute-based, and relation-based access control models. Cedar’s policy structure enables access requests to be decided quickly. Cedar’s policy validator leverages optional typing to help policy writers avoid mistakes, but not get in their way. Cedar’s design has been finely balanced to allow for a sound and complete logical encoding, which enables precise policy analysis, e.g., to ensure that when refactoring a set of policies, the authorized permissions do not change. We have modeled Cedar in the Lean programming language, and used Lean’s proof assistant to prove important properties of Cedar’s design. We have implemented Cedar in Rust, and released it open-source. Comparing Cedar to two open-source languages, OpenFGA and Rego, we find (subjectively) that Cedar has equally or more readable policies, but (objectively) performs far better.
- 24 June 2020
- Published by Springer Nature
- Vol. 12166, 13-31
An SMT Theory of Fixed-Point Arithmetic
Fixed-point arithmetic is a popular alternative to floating-point arithmetic on embedded systems. Existing work on the verification of fixed-point programs relies on custom formalizations of fixed-point arithmetic, which makes it hard to compare the described techniques or reuse the implementations. In this paper, we address this issue by proposing and formalizing an SMT theory of fixed-point arithmetic. We present an intuitive yet comprehensive syntax of the fixed-point theory, and provide formal semantics for it based on rational arithmetic. We also describe two decision procedures for this theory: one based on the theory of bit-vectors and the other on the theory of reals. We implement the two decision procedures, and evaluate our implementations using existing mature SMT solvers on a benchmark suite we created. Finally, we perform a case study of using the theory we propose to verify properties of quantized neural networks.
- 24 June 2020
- Published by Springer Nature
- Vol. 12166, 13-31
An SMT Theory of Fixed-Point Arithmetic
Fixed-point arithmetic is a popular alternative to floating-point arithmetic on embedded systems. Existing work on the verification of fixed-point programs relies on custom formalizations of fixed-point arithmetic, which makes it hard to compare the described techniques or reuse the implementations. In this paper, we address this issue by proposing and formalizing an SMT theory of fixed-point arithmetic. We present an intuitive yet comprehensive syntax of the fixed-point theory, and provide formal semantics for it based on rational arithmetic. We also describe two decision procedures for this theory: one based on the theory of bit-vectors and the other on the theory of reals. We implement the two decision procedures, and evaluate our implementations using existing mature SMT solvers on a benchmark suite we created. Finally, we perform a case study of using the theory we propose to verify properties of quantized neural networks.
- 13 January 2020
- Published by Springer Nature
- p. 90-111
Leveraging Compiler Intermediate Representation for Multi- and Cross-Language Verification
- 13 January 2020
- Published by Springer Nature
- p. 90-111
Leveraging Compiler Intermediate Representation for Multi- and Cross-Language Verification
- 3 August 2019
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 76-84
Stochastic Local Search for Solving Floating-Point Constraints
- 3 August 2019
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 76-84
Stochastic Local Search for Solving Floating-Point Constraints
- Open Access
ct-fuzz: Fuzzing for Timing Leaks
Testing-based methodologies like fuzzing are able to analyze complex software which is not amenable to traditional formal approaches like verification, model checking, and abstract interpretation. Despite enormous success at exposing countless security vulnerabilities in many popular software projects, applications of testing-based approaches have mainly targeted checking traditional safety properties like memory safety. While unquestionably important, this class of properties does not precisely characterize other important security aspects such as information leakage, e.g., through side channels. In this work we extend testing-based software analysis methodologies to two-safety properties, which enables the precise discovery of information leaks in complex software. In particular, we present the ct-fuzz tool, which lends coverage-guided greybox fuzzers the ability to detect two-safety property violations. Our approach is capable of exposing violations to any two-safety property expressed as equality between two program traces. Empirically, we demonstrate that ct-fuzz swiftly reveals timing leaks in popular cryptographic implementations.
Open Accessct-fuzz: Fuzzing for Timing Leaks
Testing-based methodologies like fuzzing are able to analyze complex software which is not amenable to traditional formal approaches like verification, model checking, and abstract interpretation. Despite enormous success at exposing countless security vulnerabilities in many popular software projects, applications of testing-based approaches have mainly targeted checking traditional safety properties like memory safety. While unquestionably important, this class of properties does not precisely characterize other important security aspects such as information leakage, e.g., through side channels. In this work we extend testing-based software analysis methodologies to two-safety properties, which enables the precise discovery of information leaks in complex software. In particular, we present the ct-fuzz tool, which lends coverage-guided greybox fuzzers the ability to detect two-safety property violations. Our approach is capable of exposing violations to any two-safety property expressed as equality between two program traces. Empirically, we demonstrate that ct-fuzz swiftly reveals timing leaks in popular cryptographic implementations.
- 19 November 2017
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 534-553
Counterexample-Guided Bit-Precision Selection
- 19 November 2017
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 534-553
Counterexample-Guided Bit-Precision Selection
- 18 July 2017
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 60 (1) , 23-42
Verifying Relative Safety, Accuracy, and Termination for Program Approximations
- 18 July 2017
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 60 (1) , 23-42
Verifying Relative Safety, Accuracy, and Termination for Program Approximations
- 4 June 2016
- Published by Springer Nature
- p. 237-254
Verifying Relative Safety, Accuracy, and Termination for Program Approximations
- 4 June 2016
- Published by Springer Nature
- p. 237-254
Verifying Relative Safety, Accuracy, and Termination for Program Approximations