Change Pattern Detection for Optimising Incremental Static Analysis

Cindy Wauters; Jens Van der Plas; Quentin Stiévenart; Coen De Roover

doi:10.1109/SCAM59687.2023.00016

Change Pattern Detection for Optimising Incremental Static Analysis

Cindy Wauters, Jens Van der Plas, Quentin Stiévenart, Coen De Roover

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

2 Citations (Scopus)

Abstract

Static analyses can be used by developers to compute properties of a program, enabling e.g., bug detection and program verification. However, reanalysing a program from scratch upon every change is time-consuming, especially in settings where code changes often, such as within IDEs. To avoid such full reanalyses, incremental analyses instead reuse parts of the previous analysis result, and reanalyse the changed code as necessary.

While incrementality improves the analysis time, we introduce a complementary approach that further reduces the analysis time. A traditional incremental analysis updates previous analysis results without domain-specific knowledge. However, the effect of particular source code changes on analysis results can be predicted. Performing a traditional incremental analysis of the changed code might therefore be unnecessary. Instead, we propose to detect code change patterns of which the effect on analysis results can be predicted and to update these results accordingly, saving potentially expensive computations.

In this paper, we explore the idea of adapting the analysis results for behaviour-preserving change patterns. In particular, we consider consistent renamings, inverted conditionals, and moved function definitions within Scheme programs. We implemented our approach and evaluated it on 30 programs. We show decreases in incremental analysis time between 3% and 99% on 25 programs that contain at least one behaviour-preserving change pattern.

Original language	English
Title of host publication	SCAM 23rd IEEE International Working Conference on Source Code Analysis and Manipulation
Editors	Leon Moonen, Christian Newman, Alessandra Gorla
Publisher	IEEE
Pages	49-60
Number of pages	12
ISBN (Electronic)	979-8-3503-0506-7
DOIs	https://doi.org/10.1109/SCAM59687.2023.00016
Publication status	Published - Oct 2023
Event	23rd IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2023) - Bogotá, Colombia Duration: 2 Oct 2023 → 3 Oct 2023 Conference number: 23 https://www.ieee-scam.org/2023/

Publication series

Name	Proceedings - 2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation, SCAM 2023

Conference

Conference	23rd IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2023)
Abbreviated title	SCAM
Country/Territory	Colombia
City	Bogotá
Period	2/10/23 → 3/10/23
Internet address	https://www.ieee-scam.org/2023/

Bibliographical note

Funding Information:
ACKNOWLEDGEMENTS This work was partially supported by Research Foundation - Flanders (FWO) (grant number 11F4822N), by CS ICON project APAX, and by "Cybersecurity Initiative Flanders".

Publisher Copyright:
© 2023 IEEE.

Keywords

Static Program Analysis
Incremental analysis
Refactoring
modular analysis

Access to Document

10.1109/SCAM59687.2023.00016

http://soft.vub.ac.be/Publications/2023/vub-tr-soft-23-13.pdf

Cite this

Wauters, C., Van der Plas, J., Stiévenart, Q., & De Roover, C. (2023). Change Pattern Detection for Optimising Incremental Static Analysis. In L. Moonen, C. Newman, & A. Gorla (Eds.), SCAM 23rd IEEE International Working Conference on Source Code Analysis and Manipulation (pp. 49-60). (Proceedings - 2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation, SCAM 2023). IEEE. https://doi.org/10.1109/SCAM59687.2023.00016

Wauters, Cindy ; Van der Plas, Jens ; Stiévenart, Quentin ; De Roover, Coen. / Change Pattern Detection for Optimising Incremental Static Analysis. SCAM 23rd IEEE International Working Conference on Source Code Analysis and Manipulation. editor / Leon Moonen ; Christian Newman ; Alessandra Gorla. IEEE, 2023. pp. 49-60 (Proceedings - 2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation, SCAM 2023).

@inproceedings{512e1c8560a648ecbdee1f018cf06b31,

title = "Change Pattern Detection for Optimising Incremental Static Analysis",

abstract = "Static analyses can be used by developers to compute properties of a program, enabling e.g., bug detection and program verification. However, reanalysing a program from scratch upon every change is time-consuming, especially in settings where code changes often, such as within IDEs. To avoid such full reanalyses, incremental analyses instead reuse parts of the previous analysis result, and reanalyse the changed code as necessary.While incrementality improves the analysis time, we introduce a complementary approach that further reduces the analysis time. A traditional incremental analysis updates previous analysis results without domain-specific knowledge. However, the effect of particular source code changes on analysis results can be predicted. Performing a traditional incremental analysis of the changed code might therefore be unnecessary. Instead, we propose to detect code change patterns of which the effect on analysis results can be predicted and to update these results accordingly, saving potentially expensive computations.In this paper, we explore the idea of adapting the analysis results for behaviour-preserving change patterns. In particular, we consider consistent renamings, inverted conditionals, and moved function definitions within Scheme programs. We implemented our approach and evaluated it on 30 programs. We show decreases in incremental analysis time between 3% and 99% on 25 programs that contain at least one behaviour-preserving change pattern.",

keywords = "Static Program Analysis, Incremental analysis, Refactoring, modular analysis",

author = "Cindy Wauters and {Van der Plas}, Jens and Quentin Sti{\'e}venart and {De Roover}, Coen",

note = "Funding Information: ACKNOWLEDGEMENTS This work was partially supported by Research Foundation - Flanders (FWO) (grant number 11F4822N), by CS ICON project APAX, and by {"}Cybersecurity Initiative Flanders{"}. Publisher Copyright: {\textcopyright} 2023 IEEE.; 23rd IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2023), SCAM ; Conference date: 02-10-2023 Through 03-10-2023",

year = "2023",

month = oct,

doi = "10.1109/SCAM59687.2023.00016",

language = "English",

series = "Proceedings - 2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation, SCAM 2023",

publisher = "IEEE",

pages = "49--60",

editor = "Leon Moonen and Christian Newman and Alessandra Gorla",

booktitle = "SCAM 23rd IEEE International Working Conference on Source Code Analysis and Manipulation",

url = "https://www.ieee-scam.org/2023/",

}

Wauters, C , Van der Plas, J, Stiévenart, Q & De Roover, C 2023, Change Pattern Detection for Optimising Incremental Static Analysis. in L Moonen, C Newman & A Gorla (eds), SCAM 23rd IEEE International Working Conference on Source Code Analysis and Manipulation. Proceedings - 2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation, SCAM 2023, IEEE, pp. 49-60, 23rd IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2023), Bogotá, Colombia, 2/10/23. https://doi.org/10.1109/SCAM59687.2023.00016

Change Pattern Detection for Optimising Incremental Static Analysis. / Wauters, Cindy ; Van der Plas, Jens; Stiévenart, Quentin; De Roover, Coen.

SCAM 23rd IEEE International Working Conference on Source Code Analysis and Manipulation. ed. / Leon Moonen; Christian Newman; Alessandra Gorla. IEEE, 2023. p. 49-60 (Proceedings - 2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation, SCAM 2023).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper

TY - GEN

T1 - Change Pattern Detection for Optimising Incremental Static Analysis

AU - Wauters, Cindy

AU - Van der Plas, Jens

AU - Stiévenart, Quentin

AU - De Roover, Coen

N1 - Conference code: 23

PY - 2023/10

Y1 - 2023/10

N2 - Static analyses can be used by developers to compute properties of a program, enabling e.g., bug detection and program verification. However, reanalysing a program from scratch upon every change is time-consuming, especially in settings where code changes often, such as within IDEs. To avoid such full reanalyses, incremental analyses instead reuse parts of the previous analysis result, and reanalyse the changed code as necessary.While incrementality improves the analysis time, we introduce a complementary approach that further reduces the analysis time. A traditional incremental analysis updates previous analysis results without domain-specific knowledge. However, the effect of particular source code changes on analysis results can be predicted. Performing a traditional incremental analysis of the changed code might therefore be unnecessary. Instead, we propose to detect code change patterns of which the effect on analysis results can be predicted and to update these results accordingly, saving potentially expensive computations.In this paper, we explore the idea of adapting the analysis results for behaviour-preserving change patterns. In particular, we consider consistent renamings, inverted conditionals, and moved function definitions within Scheme programs. We implemented our approach and evaluated it on 30 programs. We show decreases in incremental analysis time between 3% and 99% on 25 programs that contain at least one behaviour-preserving change pattern.

AB - Static analyses can be used by developers to compute properties of a program, enabling e.g., bug detection and program verification. However, reanalysing a program from scratch upon every change is time-consuming, especially in settings where code changes often, such as within IDEs. To avoid such full reanalyses, incremental analyses instead reuse parts of the previous analysis result, and reanalyse the changed code as necessary.While incrementality improves the analysis time, we introduce a complementary approach that further reduces the analysis time. A traditional incremental analysis updates previous analysis results without domain-specific knowledge. However, the effect of particular source code changes on analysis results can be predicted. Performing a traditional incremental analysis of the changed code might therefore be unnecessary. Instead, we propose to detect code change patterns of which the effect on analysis results can be predicted and to update these results accordingly, saving potentially expensive computations.In this paper, we explore the idea of adapting the analysis results for behaviour-preserving change patterns. In particular, we consider consistent renamings, inverted conditionals, and moved function definitions within Scheme programs. We implemented our approach and evaluated it on 30 programs. We show decreases in incremental analysis time between 3% and 99% on 25 programs that contain at least one behaviour-preserving change pattern.

KW - Static Program Analysis

KW - Incremental analysis

KW - Refactoring

KW - modular analysis

UR - http://www.scopus.com/inward/record.url?scp=85182742480&partnerID=8YFLogxK

U2 - 10.1109/SCAM59687.2023.00016

DO - 10.1109/SCAM59687.2023.00016

M3 - Conference paper

T3 - Proceedings - 2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation, SCAM 2023

SP - 49

EP - 60

BT - SCAM 23rd IEEE International Working Conference on Source Code Analysis and Manipulation

A2 - Moonen, Leon

A2 - Newman, Christian

A2 - Gorla, Alessandra

PB - IEEE

T2 - 23rd IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2023)

Y2 - 2 October 2023 through 3 October 2023

ER -

Wauters C , Van der Plas J, Stiévenart Q, De Roover C. Change Pattern Detection for Optimising Incremental Static Analysis. In Moonen L, Newman C, Gorla A, editors, SCAM 23rd IEEE International Working Conference on Source Code Analysis and Manipulation. IEEE. 2023. p. 49-60. (Proceedings - 2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation, SCAM 2023). https://doi.org/10.1109/SCAM59687.2023.00016

Change Pattern Detection for Optimising Incremental Static Analysis

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

VLAAI2: Subsidie Onderzoeksprogramma "Cybersecurity Initiative Flanders"

VLAAI4: CS ICON Project APAX : Automated Posture Analysis that Scales

FWOTM979: Incremental Static Program Analysis through Modularity