More Web Proxy on the site http://driver.im/

research-article

Shadow of a doubt: testing for divergences between software versions

Authors:

Hristina Palikareva,

Cristian CadarAuthors Info & Claims

ICSE '16: Proceedings of the 38th International Conference on Software Engineering

Pages 1181 - 1192

https://doi.org/10.1145/2884781.2884845

Published: 14 May 2016 Publication History

Abstract

While developers are aware of the importance of comprehensively testing patches, the large effort involved in coming up with relevant test cases means that such testing rarely happens in practice. Furthermore, even when test cases are written to cover the patch, they often exercise the same behaviour in the old and the new version of the code.

In this paper, we present a symbolic execution-based technique that is designed to generate test inputs that cover the new program behaviours introduced by a patch. The technique works by executing both the old and the new version in the same symbolic execution instance, with the old version shadowing the new one. During this combined shadow execution, whenever a branch point is reached where the old and the new version diverge, we generate a test case exercising the divergence and comprehensively test the new behaviours of the new version.

We evaluate our technique on the Coreutils patches from the CoREBench suite of regression bugs, and show that it is able to generate test inputs that exercise newly added behaviours and expose some of the regression bugs.

References

[1]

D. Babić, L. Martignoni, S. McCamant, and D. Song. Statically-directed dynamic automated test generation. In Proc. of the International Symposium on Software Testing and Analysis (ISSTA'11), July 2011.

Digital Library

[2]

M. Böhme, B. C. d. S. Oliveira, and A. Roychoudhury. Partition-based regression verification. In Proc. of the 35th International Conference on Software Engineering (ICSE'13), May 2013.

Digital Library

[3]

M. Böhme, B. C. d. S. Oliveira, and A. Roychoudhury. Regression tests to expose change interaction errors. In Proc. of the joint meeting of the European Software Engineering Conference and the ACM Symposium on the Foundations of Software Engineering (ESEC/FSE'13), Aug. 2013.

Digital Library

[4]

M. Böhme and A. Roychoudhury. Corebench: Studying complexity of regression errors". In Proc. of the International Symposium on Software Testing and Analysis (ISSTA'14), July 2014.

Digital Library

[5]

C. Cadar, D. Dunbar, and D. Engler. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proc. of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI'08), Dec. 2008.

Digital Library

[6]

C. Cadar and H. Palikareva. Shadow symbolic execution for better testing of evolving software. In Proc. of the 36th International Conference on Software Engineering, New Ideas and Emerging Results (ICSE NIER'14), May 2014.

Digital Library

[7]

C. Cadar and K. Sen. Symbolic execution for software testing: three decades later. Communications of the Association for Computing Machinery (CACM), 56(2):82--90, 2013.

Digital Library

[8]

M. d'Amorim, S. Lauterburg, and D. Marinov. Delta execution for efficient state-space exploration of object-oriented programs. In Proc. of the International Symposium on Software Testing and Analysis (ISSTA'07), July 2007.

Digital Library

[9]

P. Godefroid, N. Klarlund, and K. Sen. DART: Directed automated random testing. In Proc. of the Conference on Programing Language Design and Implementation (PLDI'05), June 2005.

Digital Library

[10]

R. Gupta, M. J. Harrold, and M. L. Soffa. Program slicing-based regression testing techniques. Software Testing Verification and Reliability (STVR), 6:83--112, 1996.

[11]

K. J. Hayhurst, D. S. Veerhusen, J. J. Chilenski, and L. K. Rierson. A practical tutorial on modified condition/decision coverage. Technical Report NASA/TM-2001-210876, NASA, 2001.

[12]

P. Hosek and C. Cadar. Safe software updates via multi-version execution. In Proc. of the 35th International Conference on Software Engineering (ICSE'13), May 2013.

Digital Library

[13]

P. Hosek and C. Cadar. Varan the Unbelievable: An efficient N-version execution framework. In Proc. of the 20th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'15), Mar. 2015.

Digital Library

[14]

C. H. P. Kim, S. Khurshid, and D. Batory. Shared execution for efficiently testing product lines. In Proc. of the 23rd International Symposium on Software Reliability Engineering (ISSRE'12), Nov. 2012.

Digital Library

[15]

M. Kim and D. Notkin. Program element matching for multi-version program analyses. In Proc. of the 2006 International Workshop on Mining Software Repositories (MSR'06), May 2006.

Digital Library

[16]

W. Le and S. D. Pattison. Patch verification via multiversion interprocedural control flow graphs. In Proc. of the 36th International Conference on Software Engineering (ICSE'14), May 2014.

Digital Library

[17]

K.-K. Ma, Y. P. Khoo, J. S. Foster, and M. Hicks. Directed symbolic execution. In Proc. of the 18th International Static Analysis Symposium (SAS'11), Sept. 2011.

Digital Library

[18]

P. D. Marinescu and C. Cadar. High-coverage symbolic patch testing. In Proc. of the 19th International SPIN Workshop on Model Checking of Software (SPIN'12), July 2012.

Digital Library

[19]

P. D. Marinescu and C. Cadar. make test-zesti: A symbolic execution solution for improving regression testing. In Proc. of the 34th International Conference on Software Engineering (ICSE'12), June 2012.

Digital Library

[20]

P. D. Marinescu and C. Cadar. KATCH: High-coverage testing of software patches. In Proc. of the joint meeting of the European Software Engineering Conference and the ACM Symposium on the Foundations of Software Engineering (ESEC/FSE'13), Aug. 2013.

Digital Library

[21]

P. D. Marinescu, P. Hosek, and C. Cadar. Covrig: A framework for the analysis of code, test, and coverage evolution in real software. In Proc. of the International Symposium on Software Testing and Analysis (ISSTA'14), July 2014.

Digital Library

[22]

M. Maurer and D. Brumley. TACHYON: Tandem execution for efficient live patch testing. In Proc. of the 21st USENIX Security Symposium (USENIX Security'12), Aug. 2012.

Digital Library

[23]

N. Partush and E. Yahav. Abstract semantic differencing via speculative correlation. In Proc. of the 29th Annual Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'14), Oct. 2014.

Digital Library

[24]

S. Person, M. B. Dwyer, S. Elbaum, and C. S. Păsăreanu. Differential symbolic execution. In Proc. of the ACM Symposium on the Foundations of Software Engineering (FSE'08), Nov. 2008.

Digital Library

[25]

S. Person, G. Yang, N. Rungta, and S. Khurshid. Directed incremental symbolic execution. In Proc. of the Conference on Programing Language Design and Implementation (PLDI'11), June 2011.

Digital Library

[26]

R. Santelices, P. K. Chittimalli, T. Apiwattanapong, A. Orso, and M. J. Harrold. Test-suite augmentation for evolving software. In Proc. of the 23rd IEEE International Conference on Automated Software Engineering (ASE'08), Sept. 2008.

Digital Library

[27]

K. Sen, D. Marinov, and G. Agha. CUTE: A concolic unit testing engine for C. In Proc. of the joint meeting of the European Software Engineering Conference and the ACM Symposium on the Foundations of Software Engineering (ESEC/FSE'05), Sept. 2005.

[28]

K. Serebryany, D. Bruening, A. Potapenko, and D. Vyukov. AddressSanitizer: A fast address sanity checker. In Proc. of the 2012 USENIX Annual Technical Conference (USENIX ATC'12), June 2012.

Digital Library

[29]

K. Taneja, T. Xie, N. Tillmann, and J. de Halleux. eXpress: guided path exploration for efficient regression test generation. In Proc. of the International Symposium on Software Testing and Analysis (ISSTA'11), July 2011.

Digital Library

[30]

J. Tucek, W. Xiong, and Y. Zhou. Efficient online validation with delta execution. In Proc. of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'09), Mar. 2009.

Digital Library

[31]

Z. Xu and G. Rothermel. Directed test suite augmentation. In Proc. of the 16th Asia-Pacific Software Engineering Conference (ASPEC'09), Dec. 2009.

Digital Library

Cited By

Postolski IBraberman VGarbervetsky DUchitel Sd'Amorim M(2024)Verification of Programs with Common FragmentsCompanion Proceedings of the 32nd ACM International Conference on the Foundations of Software Engineering10.1145/3663529.3663783(487-491)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3663529.3663783
Yi QYu YYang G(2024)Compatible Branch Coverage Driven Symbolic Execution for Efficient Bug FindingProceedings of the ACM on Programming Languages10.1145/36564438:PLDI(1633-1655)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656443
Zheng MShi QLiu XXu XYu LLiu CWei GZhang X(2024)ParDiff: Practical Static Differential Analysis of Network Protocol ParsersProceedings of the ACM on Programming Languages10.1145/36498548:OOPSLA1(1208-1234)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649854
Show More Cited By

Index Terms

Shadow of a doubt: testing for divergences between software versions
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Shadow Symbolic Execution for Testing Software Patches

While developers are aware of the importance of comprehensively testing patches, the large effort involved in coming up with relevant test cases means that such testing rarely happens in practice. Furthermore, even when test cases are written to cover ...
Shadow symbolic execution for better testing of evolving software
ICSE Companion 2014: Companion Proceedings of the 36th International Conference on Software Engineering

In this idea paper, we propose a novel way for improving the testing of program changes via symbolic execution. At a high-level, our technique runs two different program versions in the same symbolic execution instance, with the old version effectively ...
SARATHI: Characterization Study on Regression Bugs and Identification of Regression Bug Inducing Changes: A Case-Study on Google Chromium Project
ISEC '15: Proceedings of the 8th India Software Engineering Conference

As a software system evolves, maintaining the system becomes increasingly difficult. A lot of times code changes or system patches cause an existing feature to misbehave or fail completely. An issue ticket reporting a defect in a feature that was ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '16: Proceedings of the 38th International Conference on Software Engineering

May 2016

1235 pages

ISBN:9781450339001

DOI:10.1145/2884781

General Chair:
Laura Dillon
Michigan State University
,
Program Chairs:
Willem Visser
Stellenbosch University, South Africa
,
Laurie Williams
North Carolina State University

Copyright © 2016 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 the author(s) 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

ACM: Association for Computing Machinery
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS\TCSE: TC on Software Engineering
IEEE-CS\DATC: IEEE Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 May 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ICSE '16

Sponsor:

ACM
SIGSOFT
IEEE-CS\TCSE
IEEE-CS\DATC

ICSE '16: 38th International Conference on Software Engineering

May 14 - 22, 2016

Texas, Austin

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
513
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Postolski IBraberman VGarbervetsky DUchitel Sd'Amorim M(2024)Verification of Programs with Common FragmentsCompanion Proceedings of the 32nd ACM International Conference on the Foundations of Software Engineering10.1145/3663529.3663783(487-491)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3663529.3663783
Yi QYu YYang G(2024)Compatible Branch Coverage Driven Symbolic Execution for Efficient Bug FindingProceedings of the ACM on Programming Languages10.1145/36564438:PLDI(1633-1655)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656443
Zheng MShi QLiu XXu XYu LLiu CWei GZhang X(2024)ParDiff: Practical Static Differential Analysis of Network Protocol ParsersProceedings of the ACM on Programming Languages10.1145/36498548:OOPSLA1(1208-1234)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649854
Ruan HNguyen HShariffdeen RNoller YRoychoudhury A(2024)Evolutionary Testing for Program Repair2024 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST60714.2024.00058(105-116)Online publication date: 27-May-2024
https://doi.org/10.1109/ICST60714.2024.00058
Deng SLi MTang YWang SYan SZhang YCalandrino JTroncoso C(2023)CIPHERHProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620620(6843-6860)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620620
Ismayilzada ERahman MKim DYi J(2023)Poracle: Testing Patches under Preservation Conditions to Combat the Overfitting Problem of Program RepairACM Transactions on Software Engineering and Methodology10.1145/362529333:2(1-39)Online publication date: 26-Sep-2023
https://dl.acm.org/doi/10.1145/3625293
Daniel LBardin SRezk T(2023)Binsec/Rel: Symbolic Binary Analyzer for Security with Applications to Constant-Time and Secret-ErasureACM Transactions on Privacy and Security10.1145/356303726:2(1-42)Online publication date: 14-Apr-2023
https://dl.acm.org/doi/10.1145/3563037
Muylaert WHärtel JDe Roover C(2023)Symbolic Execution to Detect Semantic Merge Conflicts2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM59687.2023.00028(186-197)Online publication date: 2-Oct-2023
https://doi.org/10.1109/SCAM59687.2023.00028
Wen JMahmud TChe MYan YYang G(2023)Intelligent Constraint Classification for Symbolic Execution2023 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER56733.2023.00023(144-154)Online publication date: Mar-2023
https://doi.org/10.1109/SANER56733.2023.00023
Yu JWu YXie XLe WMa LChen YHu JZhang F(2023)GameRTS: A Regression Testing Framework for Video Games2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE)10.1109/ICSE48619.2023.00122(1393-1404)Online publication date: May-2023
https://doi.org/10.1109/ICSE48619.2023.00122
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