research-article

Efficient purely-dynamic information flow analysis

Authors:

Thomas H. Austin,

Cormac FlanaganAuthors Info & Claims

PLAS '09: Proceedings of the ACM SIGPLAN Fourth Workshop on Programming Languages and Analysis for Security

Pages 113 - 124

https://doi.org/10.1145/1554339.1554353

Published: 15 June 2009 Publication History

Abstract

We present a novel approach for efficiently tracking information flow in a dynamically-typed language such as JavaScript. Our approach is purely dynamic, and it detects problems with implicit paths via a dynamic check that avoids the need for an approximate static analyses while still guaranteeing non-interference. We incorporate this check into an efficient evaluation strategy based on sparse information labeling that leaves information flow labels implicit whenever possible, and introduces explicit labels only for values that migrate between security domains. We present experimental results showing that, on a range of small benchmark programs, sparse labeling provides a substantial (30%--50%) speed-up over universal labeling.

References

[1]

Aslan Askarov, Sebastian Hunt, Andrei Sabelfeld, and David Sands. Termination-insensitive noninterference leaks more than just a bit. In ESORICS '08: Proceedings of the 13th European Symposium on Research in Computer Security, pages 333--348, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

[2]

Anindya Banerjee and David A. Naumann. Secure information flow and pointer confinement in a java-like language. In IEEE Computer Security Foundations Workshop, pages 253--267. IEEE Computer Society, 2002.

Digital Library

[3]

Gilles Barthe, Pedro R. D'Argenio, and Tamara Rezk. Secure information flow by self-composition. In IEEE Computer Security Foundations Workshop, pages 100--114. IEEE Computer Society, 2004.

Digital Library

[4]

Gérard Boudol. Secure information flow as a safety property. In Pierpaolo Degano, Joshua D. Guttman, and Fabio Martinelli, editors, Formal Aspects in Security and Trust, volume 5491 of Lecture Notes in Computer Science, pages 20--34. Springer, 2008.

Digital Library

[5]

Deepak Chandra and Michael Franz. Fine-grained information flow analysis and enforcement in a java virtual machine. pages 463--475, Dec. 2007.

Digital Library

[6]

Stephen Chong and Andrew C. Myers. Security policies for down-grading. In CCS '04: Proceedings of the 11th ACM conference on Computer and communications security, pages 198--209, New York, NY, USA, 2004. ACM.

Digital Library

[7]

Dorothy E. Denning. A lattice model of secure information flow. Communications of the ACM, 19(5):236--243, 1976.

Digital Library

[8]

Dorothy E. Denning and Peter J. Denning. Certification of programs for secure information flow. Communications of the ACM, 20(7):504--513, 1977.

Digital Library

[9]

Brendan Eich. Narcissus--JS implemented in JS. Available on the web at http://mxr.mozilla.org/mozilla/source/js/narcissus/.

[10]

J. S. Fenton. Memoryless subsystems. The Computer Journal, 17 (2):143--147, 1974.

[11]

Robert Bruce Findler. Behavioral Software Contracts. PhD thesis, Rice University, 2002.

Digital Library

[12]

Cédric Fournet and Tamara Rezk. Cryptographically sound implementations for typed information-flow security. In Symposium on Principles of Programming Languages, pages 323--335, 2008.

Digital Library

[13]

Andreas Gal, Brendan Eich, Mike Shaver, David Anderson, Blake Kaplan, Graydon Hoare, David Mandelin, Boris Zbarsky, Jason Orendorff, Michael Bebenita, Mason Chang, Michael Franz, Edwin Smith, Rick Reitmaier, and Mohammad Haghighat. Trace-based just-in-time type specialization for dynamic languages. In Conference on Programming Language Design and Implementation, 2009.

Digital Library

[14]

Joseph A. Goguen and Jose Meseguer. Security policies and security models. IEEE Symposium on Security and Privacy, 0:11, 1982.

[15]

Kathryn E. Gray, Robert Bruce Findler, and Matthew Flatt. Fine-grained interoperability through mirrors and contracts. In OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 231--245, 2005.

Digital Library

[16]

Vivek Haldar, Deepak Chandra, and Michael Franz. Dynamic taint propagation for java. In ACSAC, pages 303--311. IEEE Computer Society, 2005.

Digital Library

[17]

Nevin Heintze and Jon G. Riecke. The slam calculus: Programming with secrecy and integrity. In Symposium on Principles of Programming Languages, pages 365--377, 1998.

Digital Library

[18]

Dave King, Boniface Hicks, Michael Hicks, and Trent Jaeger. Implicit flows: Can't live with 'em, can't live without 'em. In International Conference on Information Systems Security, pages 56--70, 2008.

Digital Library

[19]

Monica S. Lam, Michael Martin, V. Benjamin Livshits, and John Whaley. Securing web applications with static and dynamic information flow tracking. In Robert Glück and Oege de Moor, editors, ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, pages 3--12. ACM, 2008.

Digital Library

[20]

Gurvan Le Guernic, Anindya Banerjee, Thomas Jensen, and David Schmidt. Automata-based confidentiality monitoring. 2006. URL http://hal.inria.fr/inria-00130210/en/.

Digital Library

[21]

Pasquale Malacaria and Han Chen. Lagrange multipliers and maximum information leakage in different observational models. In ACM SIGPLAN Workshop on Programming Languages and Analysis for Security, pages 135--146, 2008.

Digital Library

[22]

John McLean. Proving noninterference and functional correctness using traces. Journal of Computer Security, 1(1):37--58, 1992.

Digital Library

[23]

Andrew C. Myers. Jflow: Practical mostly-static information flow control. In Symposium on Principles of Programming Languages, pages 228--241, 1999.

Digital Library

[24]

Andrew C. Myers and Barbara Liskov. A decentralized model for information flow control. In Symposium on Operating System Principles, pages 129--142, 1997.

Digital Library

[25]

Kevin R. O'Neill, Michael R. Clarkson, and Stephen Chong. Information-flow security for interactive programs. In IEEE Computer Security Foundations Workshop, pages 190--201. IEEE Computer Society, 2006.

Digital Library

[26]

François Pottier and Vincent Simonet. Information flow inference for ml. Transactions on Programming Languages and Systems, 25(1):117--158, 2003.

Digital Library

[27]

Andrei Sabelfeld and Andrew C. Myers. Language-based information-flow security. Selected Areas in Communications, IEEE Journal on, 21(1):5--19, Jan 2003.

Digital Library

[28]

Tachio Terauchi and Alexander Aiken. Secure information flow as a safety problem. In Chris Hankin and Igor Siveroni, editors, SAS, volume 3672 of Lecture Notes in Computer Science, pages 352--367. Springer, 2005.

Digital Library

[29]

V. N. Venkatakrishnan, Wei Xu, Daniel C. DuVarney, and R. Sekar. Provably correct runtime enforcement of non-interference properties. In Information and Communications Security, pages 332--351, 2006.

Digital Library

[30]

Philipp Vogt, Florian Nentwich, Nenad Jovanovic, Engin Kirda, Christopher Kruegel, and Giovanni Vigna. Cross site scripting prevention with dynamic data tainting and static analysis. February 2007. URL http://www.infosys.tuwien.ac.at/Staff/ek/papers/xss_prevention.pdf.

[31]

Dennis Volpano, Cynthia Irvine, and Geoffrey Smith. A sound type system for secure flow analysis. Journal of Computer Security, 4(2--3):167--187, 1996.

Digital Library

[32]

Stephan Arthur Zdancewic. Programming languages for information security. PhD thesis, Ithaca, NY, USA, 2002. Chair-Myers, Andrew.

[33]

Lantian Zheng and Andrew C. Myers. Securing nonintrusive web encryption through information flow. In ACM SIGPLAN Workshop on Programming Languages and Analysis for Security, pages 125--134, 2008.

Digital Library

Cited By

Gumarac M(2024)Extent of spending behavior, problems encountered, and financial knowledge across generational cohorts among state universities and colleges employeesInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2024.02.02411:2(230-237)Online publication date: Feb-2024
https://doi.org/10.21833/ijaas.2024.02.024
Beardsley VSridharan M(2024)Static-Dynamic Information Flow Control in RustCompanion Proceedings of the 2024 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3689491.3691820(16-18)Online publication date: 20-Oct-2024
https://dl.acm.org/doi/10.1145/3689491.3691820
Chen TSiek J(2024)Quest Complete: The Holy Grail of Gradual SecurityProceedings of the ACM on Programming Languages10.1145/36564428:PLDI(1609-1632)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656442
Show More Cited By

Index Terms

Efficient purely-dynamic information flow analysis
1. Security and privacy
  1. Systems security
    1. Information flow control
    2. Operating systems security
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

Multiple facets for dynamic information flow
POPL '12: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

JavaScript has become a central technology of the web, but it is also the source of many security problems, including cross-site scripting attacks and malicious advertising code. Central to these problems is the fact that code from untrusted sources ...
Permissive dynamic information flow analysis
PLAS '10: Proceedings of the 5th ACM SIGPLAN Workshop on Programming Languages and Analysis for Security

A key challenge in dynamic information flow analysis is handling implicit flows, where code conditional on a private variable updates a public variable x. The naive approach of upgrading x to private results in x being partially leaked, where its value ...
Efficient purely-dynamic information flow analysis

We present a novel approach for efficiently tracking information flow in a dynamically-typed language such as JavaScript. Our approach is purely dynamic, and it detects problems with implicit paths via a dynamic check that avoids the need for an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLAS '09: Proceedings of the ACM SIGPLAN Fourth Workshop on Programming Languages and Analysis for Security

June 2009

130 pages

ISBN:9781605586458

DOI:10.1145/1554339

Conference Chairs:
Stephen Chong
Harvard University
,
David Naumann
Stevens Institute of Technology

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '09

Sponsor:

SIGPLAN

PLDI '09: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 15 - 21, 2009

Dublin, Ireland

Acceptance Rates

PLAS '09 Paper Acceptance Rate 8 of 19 submissions, 42%;

Overall Acceptance Rate 43 of 77 submissions, 56%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

147
Total Citations
View Citations
774
Total Downloads

Downloads (Last 12 months)142
Downloads (Last 6 weeks)9

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gumarac M(2024)Extent of spending behavior, problems encountered, and financial knowledge across generational cohorts among state universities and colleges employeesInternational Journal of ADVANCED AND APPLIED SCIENCES10.21833/ijaas.2024.02.02411:2(230-237)Online publication date: Feb-2024
https://doi.org/10.21833/ijaas.2024.02.024
Beardsley VSridharan M(2024)Static-Dynamic Information Flow Control in RustCompanion Proceedings of the 2024 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3689491.3691820(16-18)Online publication date: 20-Oct-2024
https://dl.acm.org/doi/10.1145/3689491.3691820
Chen TSiek J(2024)Quest Complete: The Holy Grail of Gradual SecurityProceedings of the ACM on Programming Languages10.1145/36564428:PLDI(1609-1632)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656442
Lamba ATaylor MBeardsley VBambeck JBond MLin Z(2024)Cocoon: Static Information Flow Control in RustProceedings of the ACM on Programming Languages10.1145/36498178:OOPSLA1(166-193)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649817
Geraldo ECosta Seco JHildebrandt T(2023)Data-Dependent Confidentiality in DCR GraphsProceedings of the 25th International Symposium on Principles and Practice of Declarative Programming10.1145/3610612.3610619(1-13)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3610612.3610619
Runge TServetto MPotanin ASchaefer I(2022)Immutability and Encapsulation for Sound OO Information Flow ControlACM Transactions on Programming Languages and Systems10.1145/357327045:1(1-35)Online publication date: 2-Dec-2022
https://dl.acm.org/doi/10.1145/3573270
Crichton WPatrignani MAgrawala MHanrahan PJhala RDillig I(2022)Modular information flow through ownershipProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523445(1-14)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523445
McCall MBichhawat AJia L(2022)Compositional Information Flow Monitoring for Reactive Programs2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP53844.2022.00036(467-486)Online publication date: Jun-2022
https://doi.org/10.1109/EuroSP53844.2022.00036
Ghosal SShyamasundar R(2022)Preventing Privacy-Violating Information Flows in JavaScript Applications Using Dynamic LabellingInformation Systems Security10.1007/978-3-031-23690-7_12(202-219)Online publication date: 11-Dec-2022
https://doi.org/10.1007/978-3-031-23690-7_12
Geraldo E(2022)SNITCH: A Platform for Information Flow ControlIntegrated Formal Methods10.1007/978-3-031-07727-2_24(365-368)Online publication date: 1-Jun-2022
https://doi.org/10.1007/978-3-031-07727-2_24
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents