Taint propagation path analysis based on program dependency

Y. Wang; C. Wang; C. Z. Hu; C. Shan

doi:10.1201/b18049-38

Taint propagation path analysis based on program dependency

Y. Wang, C. Wang, C. Z. Hu, C. Shan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

Taint propagation path analysis is an important pre-processing part to software vulnerability detection. This paper presents a static taint propagation path analysis method based on program dependency. After transforming the source code to the SSA (Static Single Assignment) form, we make a program dependency analysis, which consists of data dependency analysis within basic blocks, control dependency analysis between basic blocks, and Phi function dependency analysis. In particular, the branch control variables calculation from control dependency analysis and Phi function dependency analysis can transform the dependency between basic blocks into dependency between variables. As a result, we obtain the global program variable dependency graph, based on which, we can further find taint propagation paths through marking tainted data.We have implemented the method on the LLVM (Low Level Virtual Machine) compiler, and the experiment results show its validity.

Original language	English
Title of host publication	Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014
Editors	Dawei Zheng
Publisher	CRC Press/Balkema
Pages	159-164
Number of pages	6
ISBN (Print)	9781138026537
DOIs	https://doi.org/10.1201/b18049-38
Publication status	Published - 2015
Event	International Conference on Future Communication, Information and Computer Science, FCICS 2014 - Beijing, China Duration: 22 May 2014 → 23 May 2014

Publication series

Name	Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014

Conference

Conference	International Conference on Future Communication, Information and Computer Science, FCICS 2014
Country/Territory	China
City	Beijing
Period	22/05/14 → 23/05/14

Keywords

Branch control variables
Control dependency
Data dependency
Phi function
SSA
Taint propagation path analysis
Value dependency graph

Access to Document

10.1201/b18049-38

Cite this

Wang, Y., Wang, C., Hu, C. Z., & Shan, C. (2015). Taint propagation path analysis based on program dependency. In D. Zheng (Ed.), Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014 (pp. 159-164). (Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014). CRC Press/Balkema. https://doi.org/10.1201/b18049-38

Wang, Y. ; Wang, C. ; Hu, C. Z. et al. / Taint propagation path analysis based on program dependency. Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014. editor / Dawei Zheng. CRC Press/Balkema, 2015. pp. 159-164 (Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014).

@inproceedings{82bc69a8f4c9426794eebd8eb80c3380,

title = "Taint propagation path analysis based on program dependency",

abstract = "Taint propagation path analysis is an important pre-processing part to software vulnerability detection. This paper presents a static taint propagation path analysis method based on program dependency. After transforming the source code to the SSA (Static Single Assignment) form, we make a program dependency analysis, which consists of data dependency analysis within basic blocks, control dependency analysis between basic blocks, and Phi function dependency analysis. In particular, the branch control variables calculation from control dependency analysis and Phi function dependency analysis can transform the dependency between basic blocks into dependency between variables. As a result, we obtain the global program variable dependency graph, based on which, we can further find taint propagation paths through marking tainted data.We have implemented the method on the LLVM (Low Level Virtual Machine) compiler, and the experiment results show its validity.",

keywords = "Branch control variables, Control dependency, Data dependency, Phi function, SSA, Taint propagation path analysis, Value dependency graph",

author = "Y. Wang and C. Wang and Hu, {C. Z.} and C. Shan",

note = "Publisher Copyright: {\textcopyright} 2015 Taylor & Francis Group, London.; International Conference on Future Communication, Information and Computer Science, FCICS 2014 ; Conference date: 22-05-2014 Through 23-05-2014",

year = "2015",

doi = "10.1201/b18049-38",

language = "English",

isbn = "9781138026537",

series = "Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014",

publisher = "CRC Press/Balkema",

pages = "159--164",

editor = "Dawei Zheng",

booktitle = "Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014",

}

Wang, Y , Wang, C , Hu, CZ & Shan, C 2015, Taint propagation path analysis based on program dependency. in D Zheng (ed.), Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014. Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014, CRC Press/Balkema, pp. 159-164, International Conference on Future Communication, Information and Computer Science, FCICS 2014, Beijing, China, 22/05/14. https://doi.org/10.1201/b18049-38

Taint propagation path analysis based on program dependency. / Wang, Y.; Wang, C.; Hu, C. Z. et al.
Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014. ed. / Dawei Zheng. CRC Press/Balkema, 2015. p. 159-164 (Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Taint propagation path analysis based on program dependency

AU - Wang, Y.

AU - Wang, C.

AU - Hu, C. Z.

AU - Shan, C.

PY - 2015

Y1 - 2015

N2 - Taint propagation path analysis is an important pre-processing part to software vulnerability detection. This paper presents a static taint propagation path analysis method based on program dependency. After transforming the source code to the SSA (Static Single Assignment) form, we make a program dependency analysis, which consists of data dependency analysis within basic blocks, control dependency analysis between basic blocks, and Phi function dependency analysis. In particular, the branch control variables calculation from control dependency analysis and Phi function dependency analysis can transform the dependency between basic blocks into dependency between variables. As a result, we obtain the global program variable dependency graph, based on which, we can further find taint propagation paths through marking tainted data.We have implemented the method on the LLVM (Low Level Virtual Machine) compiler, and the experiment results show its validity.

AB - Taint propagation path analysis is an important pre-processing part to software vulnerability detection. This paper presents a static taint propagation path analysis method based on program dependency. After transforming the source code to the SSA (Static Single Assignment) form, we make a program dependency analysis, which consists of data dependency analysis within basic blocks, control dependency analysis between basic blocks, and Phi function dependency analysis. In particular, the branch control variables calculation from control dependency analysis and Phi function dependency analysis can transform the dependency between basic blocks into dependency between variables. As a result, we obtain the global program variable dependency graph, based on which, we can further find taint propagation paths through marking tainted data.We have implemented the method on the LLVM (Low Level Virtual Machine) compiler, and the experiment results show its validity.

KW - Branch control variables

KW - Control dependency

KW - Data dependency

KW - Phi function

KW - SSA

KW - Taint propagation path analysis

KW - Value dependency graph

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

U2 - 10.1201/b18049-38

DO - 10.1201/b18049-38

M3 - Conference contribution

AN - SCOPUS:84940473809

SN - 9781138026537

T3 - Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014

SP - 159

EP - 164

BT - Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014

A2 - Zheng, Dawei

PB - CRC Press/Balkema

T2 - International Conference on Future Communication, Information and Computer Science, FCICS 2014

Y2 - 22 May 2014 through 23 May 2014

ER -

Wang Y , Wang C , Hu CZ , Shan C. Taint propagation path analysis based on program dependency. In Zheng D, editor, Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014. CRC Press/Balkema. 2015. p. 159-164. (Future Communication, Information and Computer Science - Proceedings of the International Conference on Future Communication, Information and Computer Science, FCICS 2014). doi: 10.1201/b18049-38

Taint propagation path analysis based on program dependency

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this