Abstract
The last several years have seen a proliferation of static and runtime analysis tools for finding security violations that are caused by explicit information flow in programs. Much of this interest has been caused by the increase in the number of vulnerabilities such as cross-site scripting and SQL injection. In fact, these explicit information flow vulnerabilities commonly found in Web applications now outnumber vulnerabilities such as buffer overruns common in type-unsafe languages such as C and C++. Tools checking for these vulnerabilities require a specification to operate. In most cases the task of providing such a specification is delegated to the user. Moreover, the efficacy of these tools is only as good as the specification. Unfortunately, writing a comprehensive specification presents a major challenge: parts of the specification are easy to miss, leading to missed vulnerabilities; similarly, incorrect specifications may lead to false positives.
This paper proposes Merlin, a new approach for automatically inferring explicit information flow specifications from program code. Such specifications greatly reduce manual labor, and enhance the quality of results, while using tools that check for security violations caused by explicit information flow. Beginning with a data propagation graph, which represents interprocedural flow of information in the program, Merlin aims to automatically infer an information flow specification. Merlin models information flow paths in the propagation graph using probabilistic constraints. A naive modeling requires an exponential number of constraints, one per path in the propagation graph. For scalability, we approximate these path constraints using constraints on chosen triples of nodes, resulting in a cubic number of constraints. We characterize this approximation as a probabilistic abstraction, using the theory of probabilistic refinement developed by McIver and Morgan. We solve the resulting system of probabilistic constraints using factor graphs, which are a well-known structure for performing probabilistic inference.
We experimentally validate the Merlin approach by applying it to 10 large business-critical Web applications that have been analyzed with CAT.NET, a state-of-the-art static analysis tool for .NET. We find a total of 167 new confirmed specifications, which result in a total of 322 additional vulnerabilities across the 10 benchmarks. More accurate specifications also reduce the false positive rate: in our experiments, Merlin-inferred specifications result in 13 false positives being removed; this constitutes a 15% reduction in the CAT.NET false positive rate on these 10 programs. The final false positive rate for CAT.NET after applying Merlin in our experiments drops to under 1%.
- D. Chandra and M. Franz. Fine-grained information flow analysis and enforcement in a java virtual machine. In Annual Computer Security Applications Conference, pages 463--475, 2007.Google ScholarCross Ref
- M. Dalton, H. Kannan, and C. Kozyrakis. Raksha: a flexible information flow architecture for software security. In Proceedings of the International Symposium on Computer Architecture, pages 482--493, 2007. Google ScholarDigital Library
- D. R. Engler, D. Y. Chen, and A. Chou. Bugs as inconsistent behavior: A general approach to inferring errors in systems code. In In Proceedings of ACM Symposium on Operating Systems Principles, pages 57--72, 2001. Google ScholarDigital Library
- Fortify. Fortify code analyzer. http://www.ouncelabs.com/, 2008.Google Scholar
- C. L. Goues and W. Weimer. Specification mining with few false positives. In Tools and Algorithms for the Construction and Analysis of Systems, 2009. Google ScholarDigital Library
- V. Haldar, D. Chandra, and M. Franz. Dynamic taint propagation for Java. In Proceedings of the Annual Computer Security Applications Conference, pages 303--311, Dec. 2005. Google ScholarDigital Library
- C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the ACM, 12:576--583, October 1969. Google ScholarDigital Library
- Y.-W. Huang, F. Yu, C. Hang, C.-H. Tsai, D.-T. Lee, and S.-Y. Kuo. Securing Web application code by static analysis and runtime protection. In Proceedings of the Conference on World Wide Web, pages 40--52, May 2004. Google ScholarDigital Library
- N. Jovanovic, C. Kruegel, and E. Kirda. Pixy: a static analysis tool for detecting Web application vulnerabilities (short paper). In Proceedings of the Symposium on Security and Privacy, May 2006. Google ScholarDigital Library
- T. Kremenek, P. Twohey, G. Back, A. Y. Ng, and D. R. Engler. From uncertainty to belief: Inferring the specification within. In Symposium on Operating Systems Design and Implementation, pages 161--176, Nov. 2006. Google ScholarDigital Library
- M. Krohn, A. Yip, M. Brodsky, N. Cliffer, M. F. Kaashoek, E. Kohler, and R. Morris. Information flow control for standard os abstractions. In Proceedings of Symposium on Operating Systems Principles, pages 321--334, 2007. Google ScholarDigital Library
- F. R. Kschischang, B. J. Frey, and H. A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498--519, 2001. Google ScholarDigital Library
- Z. Li and Y. Zhou. Pr-miner: Automatically extracting implicit programming rules and detecting violations in large software code. In Proceedings of the European Software Engineering Conference, 2005. Google ScholarDigital Library
- B. Livshits. Improving Software Security with Precise Static and Runtime Analysis. PhD thesis, Stanford University, Stanford, California, 2006. Google ScholarDigital Library
- B. Livshits and M. S. Lam. Finding security errors in Java programs with static analysis. In Proceedings of the Usenix Security Symposium, pages 271--286, Aug. 2005. Google ScholarDigital Library
- B. Livshits and T. Zimmermann. DynaMine: Finding common error patterns by mining software revision histories. In Proceedings of the International Symposium on the Foundations of Software Engineering, pages 296-305, Sept. 2005. Google ScholarDigital Library
- M. Martin, B. Livshits, and M. S. Lam. Finding application errors and security vulnerabilities using PQL: a program query language. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages, and Applications, Oct. 2005. Google ScholarDigital Library
- M. Martin, B. Livshits, and M. S. Lam. SecuriFly: Runtime vulnerability protection for Web applications. Technical report, Stanford University, Oct. 2006.Google Scholar
- A. McIver and C. Morgan. Abstraction, Refinement and Proof of Probabilistic Systems. Springer, 2004. Google ScholarDigital Library
- A. McIver and C. Morgan. Abstraction and refinement in probabilistic systems. SIGMETRICS Performance Evaluation Review, 32:41--47, March 2005. Google ScholarDigital Library
- Microsoft Corporation. Microsoft Code Analysis Tool .NET (CAT.NET). http://www.microsoft. com/downloads/details.aspx?FamilyId= 0178e2ef-9da8-445e-9348-c93f24cc9f9d&displaylang=en, 3 2009.Google Scholar
- T. Minka, J.Winn, J. Guiver, and A. Kannan. Infer.NET 2.2, 2009. Microsoft Research Cambridge. http://research.microsoft.com/infernet.Google Scholar
- A. Nguyen-Tuong, S. Guarnieri, D. Greene, J. Shirley, and D. Evans. Automatically hardening Web applications using precise tainting. In Proceedings of the IFIP International Information Security Conference, June 2005.Google ScholarCross Ref
- OunceLabs, Inc. Ounce. http://www.ouncelabs.com/, 2008.Google Scholar
- T. Pietraszek and C. V. Berghe. Defending against injection attacks through context-sensitive string evaluation. In Proceedings of the Recent Advances in Intrusion Detection, Sept. 2005. Google ScholarDigital Library
- M. K. Ramanathan, A. Grama, and S. Jagannathan. Static specification inference using predicate mining. In PLDI, 2007. Google ScholarDigital Library
- A. Sabelfeld and A. Myers. Language-based information-flow security. IEEE Journal on Selected Areas in Communications, 21(1):5--19, January 2003. Google ScholarDigital Library
- Z. Su and G. Wassermann. The essence of command injection attacks in web applications. In Proceedings of POPL, 2006. Google ScholarDigital Library
- S. Vandebogart, P. Efstathopoulos, E. Kohler, M. Krohn, C. Frey, D. Ziegler, F. Kaashoek, R. Morris, and D. Mazières. Labels and event processes in the Asbestos operating system. ACM Trans. Comput. Syst., 25(4):11, 2007. Google ScholarDigital Library
- L. Wall. Perl security. http://search.cpan.org/dist/perl/ pod/perlsec.pod.Google Scholar
- W.Weimer and G. C. Necula. Mining temporal specifications for error detection. In Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 461--476, 2005. Google ScholarDigital Library
- J. Whaley, M. Martin, and M. Lam. Automatic extraction of objectoriented component interfaces. In Proceedings of the International Symposium on Software Testing and Analysis, pages 218--228, 2002. Google ScholarDigital Library
- Y. Xie and A. Aiken. Static detection of security vulnerabilities in scripting languages. In Proceedings of the Usenix Security Symposium, pages 271--286, Aug. 2006. Google ScholarDigital Library
- J. Yang and D. Evans. Perracotta: mining temporal API rules from imperfect traces. In Proceedings of the International Conference on Software Engineering, pages 282--291, 2006. Google ScholarDigital Library
- J. S. Yedidia, W. T. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. Exploring Artificial Intelligence in the New Millennium, pages 239--269, 2003. Google ScholarDigital Library
- N. Zeldovich, S. Boyd-Wickizer, E. Kohler, and D. Mazires. Making information flow explicit in HiStar. In Proceedings of the Symposium on Operating Systems Design and Implementation, pages 263--278, 2006. Google ScholarDigital Library
Index Terms
- Merlin: specification inference for explicit information flow problems
Recommendations
Scalable taint specification inference with big code
PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and ImplementationWe present a new scalable, semi-supervised method for inferring taint analysis specifications by learning from a large dataset of programs. Taint specifications capture the role of library APIs (source, sink, sanitizer) and are a critical ingredient of ...
Merlin: specification inference for explicit information flow problems
PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and ImplementationThe last several years have seen a proliferation of static and runtime analysis tools for finding security violations that are caused by explicit information flow in programs. Much of this interest has been caused by the increase in the number of ...
Active learning of points-to specifications
PLDI '18When analyzing programs, large libraries pose significant challenges to static points-to analysis. A popular solution is to have a human analyst provide points-to specifications that summarize relevant behaviors of library code, which can substantially ...
Comments