research-article

Automatically identifying critical input regions and code in applications

Authors:

Michael Carbin,

Martin C. RinardAuthors Info & Claims

ISSTA '10: Proceedings of the 19th international symposium on Software testing and analysis

Pages 37 - 48

https://doi.org/10.1145/1831708.1831713

Published: 12 July 2010 Publication History

Abstract

Applications that process complex inputs often react in different ways to changes in different regions of the input. Small changes to forgiving regions induce correspondingly small changes in the behavior and output. Small changes to critical regions, on the other hand, can induce disproportionally large changes in the behavior or output. Identifying the critical and forgiving regions in the input and the corresponding critical and forgiving regions of code is directly relevant to many software engineering tasks.

We present a system, Snap, for automatically grouping related input bytes into fields and classifying each field and corresponding regions of code as critical or forgiving. Given an application and one or more inputs, Snap uses targeted input fuzzing in combination with dynamic execution and influence tracing to classify regions of input fields and code as critical or forgiving. Our experimental evaluation shows that Snap makes classifications with close to perfect precision (99%) and very good recall (between 99% and 73%, depending on the application).

References

[1]

Dave Aitel. The advantages of block-based protocol analysis for security testing. Technical report, Immunity, Inc., 2002.

[2]

Juan Caballero, Heng Yin, Zhenkai Liang, and Dawn Xiaodong Song. Polyglot: automatic extraction of protocol message format using dynamic binary analysis. In CCS, pages 317--329, 2007.

Digital Library

[3]

Jim Chow, Ben Pfaff, Tal Garfinkel, and Mendel Rosenblum. Shredding your garbage: reducing data lifetime through secure deallocation. In Security, pages 22--22, 2005.

Digital Library

[4]

James Clause, Wanchun Li, and Ro Orso. Dytan: A generic dynamic taint analysis framework. In ISSTA, pages 196--206, 2007.

Digital Library

[5]

James A. Clause and Alessandro Orso. Penumbra: automatically identifying failure-relevant inputs using dynamic tainting. In ISSTA, pages 249--260, 2009.

Digital Library

[6]

Paolo Milani Comparetti, Gilbert Wondracek, Christopher Krügel, and Engin Kirda. Prospex: Protocol specification extraction. In IEEE Symposium on Security and Privacy, pages 110--125, 2009.

Digital Library

[7]

Weidong Cui, Marcus Peinado, Karl Chen, Helen J. Wang, and Luis Irú-Briz. Tupni: automatic reverse engineering of input formats. In CCS, 2008.

Digital Library

[8]

Will Drewry and Tavis Ormandy. Flayer: exposing application internals. In WOOT, pages 1--9, 2007.

Digital Library

[9]

Vijay Ganesh, Tim Leek, and Martin Rinard. Taint-based directed whitebox fuzzing. In ICSE, 2009.

Digital Library

[10]

Henry Hoffmann, Sasa Misailovic, Stelios Sidiroglou, Anant Agarwal, and Martin Rinard. Using Code Perforation to Improve Performance, Reduce Energy Consumptio n, and Respond to Failures. Technical Report MIT-CSAIL-TR-2009-042, MIT, September 2009.

[11]

Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong program analysis & transformation. In CGO, pages 75--88, 2004.

Digital Library

[12]

Zhiqiang Lin, Xuxian Jiang, Dongyan Xu, and Xiangyu Zhang. Automatic protocol format reverse engineering through context-aware monitored execution. In NDSS, 2008.

[13]

Barton P. Miller, Louis Fredriksen, and Bryan So. An empirical study of the reliability of unix utilities. CACM, 33(12):32--44, 1990.

Digital Library

[14]

Sasa Misailovic, Deokhwan Kim, and Martin Rinard. Automatic Parallelization with Automatic Accuracy Bounds. Technical Report MIT-CSAIL-TR-2010-007, 2010.

[15]

Sasa Misailovic, Stelios Sidiroglou, Henry Hoffman, and Martin C. Rinard. Quality of service profiling. In ICSE, 2010.

Digital Library

[16]

James Newsome and Dawn Song. Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software. In NDSS, 2005.

[17]

Huu Hai Nguyen and Martin C. Rinard. Detecting and eliminating memory leaks using cyclic memory allocation. In ISMM, pages 15--30, 2007.

Digital Library

[18]

Carlos Pacheco, Shuvendu K. Lahiri, Michael D. Ernst, and Thomas Ball. Feedback-directed random test generation. In ICSE, pages 75--84, 2007.

Digital Library

[19]

Karthik Pattabiraman, Vinod Grover, and Benjamin G. Zorn. Samurai: protecting critical data in unsafe languages. In EuroSys, pages 219--232, 2008.

Digital Library

[20]

Jeff H. Perkins, Sunghun Kim, Samuel Larsen, Saman P. Amarasinghe, Jonathan Bachrach, Michael Carbin, Carlos Pacheco, Frank Sherwood, Stelios Sidiroglou, Greg Sullivan, Weng-Fai Wong, Yoav Zibin, Michael D. Ernst, and Martin C. Rinard. Automatically patching errors in deployed software. In SOSP, pages 87--102, 2009.

Digital Library

[21]

Feng Qin, Cheng Wang, Zhenmin Li, Ho-Seop Kim, Yuanyuan Zhou, and Youfeng Wu. Lift: A low-overhead practical information flow tracking system for detecting security attacks. In MICRO, pages 135--148, 2006.

Digital Library

[22]

Martin C. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In ICS, pages 324--334, 2006.

Digital Library

[23]

Martin C. Rinard. Living in the comfort zone. In OOPSLA, pages 611--622, 2007.

Digital Library

[24]

Martin C. Rinard. Using early phase termination to eliminate load imbalances at barrier synchronization points. In OOPSLA, pages 369--386, 2007.

Digital Library

[25]

Martin C. Rinard, Cristian Cadar, Daniel Dumitran, Daniel M. Roy, Tudor Leu, and William S. Beebee. Enhancing server availability and security through failure-oblivious computing. In OSDI, pages 303--316, 2004.

Digital Library

[26]

Martin C. Rinard, Cristian Cadar, and Huu Hai Nguyen. Exploring the acceptability envelope. In OOPSLA Companion, pages 21--30, 2005.

Digital Library

[27]

G. Edward Suh, Jae W. Lee, David Zhang, and Srinivas Devadas. Secure program execution via dynamic information flow tracking. In ASPLOS, pages 85--96, 2004.

Digital Library

[28]

Pang-Ning Tan, Michael Steinbach, and Vipin Kumar. Introduction to Data Mining. Addison Wesley, 2005.

Digital Library

Cited By

Rinard MRoychoudhury APaiva AAbreu RStorey M(2024)Software Engineering Research in a World with Generative Artificial IntelligenceProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3649399(1-5)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3649399
Liu YWang JYan ZWan ZJäntti R(2023)A Survey on Blockchain-Based Trust Management for Internet of ThingsIEEE Internet of Things Journal10.1109/JIOT.2023.323789310:7(5898-5922)Online publication date: 1-Apr-2023
https://doi.org/10.1109/JIOT.2023.3237893
Misailovic S(2022)Accuracy-Aware CompilersApproximate Computing Techniques10.1007/978-3-030-94705-7_7(177-214)Online publication date: 3-Jan-2022
https://doi.org/10.1007/978-3-030-94705-7_7
Show More Cited By

Index Terms

Automatically identifying critical input regions and code in applications
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

Input/output characteristics of scalable parallel applications
Supercomputing '95: Proceedings of the 1995 ACM/IEEE conference on Supercomputing

Rapid increases in computing and communication performance are exacerbating the long-standing problem of performance-limited input/output. Indeed, for many otherwise scalable parallel applications. input/output is emerging as a major performance ...
Reducing user input validation code in web applications using Pex extension
CompSysTech '14: Proceedings of the 15th International Conference on Computer Systems and Technologies

Validation of user input data is very important in web application. Not only it protects the system from various exploits, but it also improves the user experience. User immediately sees what values are missing or are not valid and should be fixed. It ...
Language choice for safety critical applications

The programming languages currently most popular among software engineers for writing safety critical applications are C and, more recently, C++. The Ada language has been designed with software safety in mind. Although Ada is not perfect concerning ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA '10: Proceedings of the 19th international symposium on Software testing and analysis

July 2010

294 pages

ISBN:9781605588230

DOI:10.1145/1831708

General Chair:
Paolo Tonella
Fondazione Bruno Kessler -- IRST, Italy
,
Program Chair:
Alessandro Orso
Georgia Institute of Technology, USA

Copyright © 2010 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

SIGSOFT: ACM Special Interest Group on Software Engineering

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '10

Sponsor:

SIGSOFT

ISSTA '10: International Symposium on Software Testing and Analysis

July 12 - 16, 2010

Trento, Italy

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
632
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rinard MRoychoudhury APaiva AAbreu RStorey M(2024)Software Engineering Research in a World with Generative Artificial IntelligenceProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3649399(1-5)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3649399
Liu YWang JYan ZWan ZJäntti R(2023)A Survey on Blockchain-Based Trust Management for Internet of ThingsIEEE Internet of Things Journal10.1109/JIOT.2023.323789310:7(5898-5922)Online publication date: 1-Apr-2023
https://doi.org/10.1109/JIOT.2023.3237893
Misailovic S(2022)Accuracy-Aware CompilersApproximate Computing Techniques10.1007/978-3-030-94705-7_7(177-214)Online publication date: 3-Jan-2022
https://doi.org/10.1007/978-3-030-94705-7_7
Teoh JGulzar MKim MFonseca RDelimitrou COoi B(2020)Influence-based provenance for dataflow applications with taint propagationProceedings of the 11th ACM Symposium on Cloud Computing10.1145/3419111.3421292(372-386)Online publication date: 12-Oct-2020
https://dl.acm.org/doi/10.1145/3419111.3421292
Wickramasinghe IKalutarage H(2020)Naive Bayes: applications, variations and vulnerabilities: a review of literature with code snippets for implementationSoft Computing10.1007/s00500-020-05297-6Online publication date: 9-Sep-2020
https://doi.org/10.1007/s00500-020-05297-6
Lee WLiu YLiu PMa SChoi HZhang XGupta RKandemir MJimborean AMoseley T(2019)White-box program tuningProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314889(122-135)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314889
Karakoy MKislal OTang XKandemir MArunachalam M(2019)Architecture-Aware Approximate ComputingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3341617.33261533:2(1-24)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3341617.3326153
De Silva HSantosa AHo NWong WChen JShrivastava A(2019)ApproxSymate: path sensitive program approximation using symbolic executionProceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3316482.3326341(148-162)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3316482.3326341
Mahmoud AVenkatagiri RAhmed KMisailovic SMarinov DFletcher CAdve SBahar IHerlihy MWitchel ELebeck A(2019)MinotaurProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304050(1087-1103)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304050
Joshi KFernando VMisailovic SAtlee JBultan TWhittle J(2019)Statistical algorithmic profiling for randomized approximate programsProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00071(608-618)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00071
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