SymVuls: シンボリック実行トレースと機械学習を用いたソフトウェアの脆弱性
検出
SymVuls: Software vulnerability
detection with symbolic execution
trace and machine learning
大久保研究室 M2
学籍番号：5593501
加納 永康 (mgs193501@iisec.ac.jp)

1Abstract• A proposal of a new
methodology to detect software
vulnerability with applying
machine learning• Achieved high-performance–AUC 0.9953 on the SARD CWE-89
dataset2

Background3

Success of Machine Learning
Machine learning is widely used and successful in many fields.
Face Recognition

Translation

Text Mining

NLP: Natural Language Processing
4Understanding Source Code<?php$mysqli = new mysqli("localhost", "u", "a", "a");$u = $_GET["user"];$p = $_GET["password"];$q = "SELECT COUNT(*) FROM USERS WHERE USER_ID = '" .
$u . "’". "AND PASSWORD = " . "'" . $p . "’";
$result = $mysqli->query($q);
if ($result->num_rows() > 0) {echo "Success";} else {echo "Wrong user-ID or password";}

Source Code

NLP
Safe

Unsafe5

Taint Analysis
1

<?php

2

$mysqli = new mysqli("localhost", "u", "a", "a");3$u = $_GET["user"];

4$p = $_GET["password"];5$q = "SELECT COUNT(*) FROM USERS WHERE USER_ID = '" . $u . "’"6AND PASSWORD = "'" . $p . "’";

7$result = $mysqli->query($q);

8if ($result->num_rows() > 0) {910echo "Success";} else {1112echo "Wrong user-ID or password";}

Untrusted Source
Tainted values
Sink
6

Taint Analysis Specifications
Vulnerable

SourceSink

SecureSource

Taint Analysis Specifications

TypeXSSSQLi

Source_GET_POST_ENV_GET_POST_ENV

Sanitizer

htmlspecialc
hars

mysqli_esca
pe_string

Sink

echo
printquery()execute()Sanitizer

Sink

Different for each vulnerability
and programing language7Machine Learning for SVP
SVP (Software Vulnerability Prediction)

1. Software Metrics
2. Text Mining Features
3. Graph Features
4. Taint Analysis Features
5. Others

ZhanJun Li, Yan Shao: A Survey of Feature Selection for Vulnerability
Prediction Using Feature-based Machine Learning, ICMLC '19: Proceedings ofthe 2019 11th International Conference on Machine Learning andComputing, P.36–42, 20198Text Mining Features
Analyze source code as text, and convert itto vector representation to feed it into themachine learning algorithm.

Text

VectorRepresentation

Word Embedding

MachineLearning

9Word Embedding for Programming Language
Jordan Henkel et al. proposed a new methodology thatuses Symbolic Execution Traces to perform high-quality
word embedding(1) SymbolicExecution(2) Abstract
Traces(3) WordEmbedding

Jordan Henkel et al., CodeVectors: Understanding Programs Through Embedded
Abstracted Symbolic Traces (2018)10Symbolic Execution"In computer science, symbolic execution (also symbolic evaluation or symbex) isa means of analyzing a program to determine what inputs cause each part of aprogram to execute."function test($a) {$v = 0;
if ($a > 2) {$v = $a * 3;printf("A:%d¥n", $v);
} else {$v = $a + 2;
printf("B:%d¥n", $v);}}$a > 2
Variable

Valuea(Input)v(Input) * 3! ($a > 2); $a <= 2
Variable

Valuea(Input)v(Input) + 2

Often referred with SMT (Satisfiability Modulo Theories), mainly for test automation,
test cases generation.
11
https://en.wikipedia.org/wiki/Symbolic_execution

Research Questions
Would vulnerability detection result be
RQ1 improved if Symbolic Execution traces are usedfor Word Embedding?

Does the trained model have enough versatility
RQ2 to detect vulnerabilities in other test sourcecode?
12Related Work

13

VulDeePecker (2018)

Word2Vec& BLSTM
learning

Zhen Li, Deqing Zou, Shouhuai Xux, Xinyu Ou, Hai Jin, Sujuan Wang, Zhijun Deng and Yuyi Zhong
VulDeePecker: A Deep Learning-Based System for Vulnerability Detection (NDSS 2018, 2018)• Using Program Slicing to extract vulnerable code
• Need to specify a “Sink” or “Source” to get the slice

14

TAP (2019)

AUC

0.9941Yong Fang, Shengjun Han, Cheng HuangID, Runpu Wu
TAP: A static analysis model for PHP vulnerabilities based on token and deep learningtechnology (2019)• Grouping of token is done in advance• Highly dependent on PHP processor, Versatility is in doubt

15

New Methodology

16Proposed Methodology
Source CodeVectors

Function Call Traces

SymbolicExecution &Simplification

sprintf ( #str# ' %s ' , )mysql_connect ( #str# , #str# , #str# )mysql_select_db ( #str# )echo ( #str# . sprintf ( #str# ' %s ' , _GET [ #str# ] ) . #str# )echo ( #str# . sprintf ( #str# ' %s ' , ) . #str# )mysql_query ( sprintf ( #str# ' %s ' , _GET [ #str# ] ) )mysql_query ( sprintf ( #str# ' %s ' , ) )echo ( #str# )echo ( #str# )echo ( #str# )echo ( #str# )…
…

WordEmbeddingecho = [-0.5185164 , -0.8347919 , 1.171482 , 0.6900932 , 0.64918447,-0.08244713, 0.5991925 , 0.10949674, -0.47637585, 0.9477746 ,-0.8089947 , -0.7869316 , 0.42289555, 0.49892744, -0.3618514 ,-1.4450327 , -0.43445647, 0.81112355, -1.177568 , 0.94679874,
0.7710409 , -0.09612622, -0.85266286, -0.46487492, 1.0379548 ,
1.0902969 , 0.21682492, -0.1771169 , 1.2194921 , 1.8131593 ,…]sprintf = [-0.5185164 , -0.8347919 , 1.171482 , 0.6900932 , 0.64918447,-0.08244713, 0.5991925 , 0.10949674, -0.47637585, 0.9477746 ,-0.8089947 , -0.7869316 , 0.42289555, 0.49892744, -0.3618514 ,-1.4450327 , -0.43445647, 0.81112355, -1.177568 , 0.94679874,
0.7710409 , -0.09612622, -0.85266286, -0.46487492, 1.0379548 ,1.0902969 , 0.21682492, -0.1771169 , 1.2194921 , 1.8131593 ,…]mysql_query = [-0.5185164 , -0.8347919 , 1.171482 , 0.6900932 , 0.64918447,-0.08244713, 0.5991925 , 0.10949674, -0.47637585, 0.9477746 ,-0.8089947 , -0.7869316 , 0.42289555, 0.49892744, -0.3618514 ,-1.4450327 , -0.43445647, 0.81112355, -1.177568 , 0.94679874,0.7710409 , -0.09612622, -0.85266286, -0.46487492, 1.0379548 ,
1.0902969 , 0.21682492, -0.1771169 , 1.2194921 , 1.8131593 ,…]…

Filtering

mysql_query = [-0.5185164 , -0.8347919 , 1.171482 , 0.6900932 , 0.64918447,-0.08244713, 0.5991925 , 0.10949674, -0.47637585, 0.9477746 ,-0.8089947 , -0.7869316 , 0.42289555, 0.49892744, -0.3618514 ,-1.4450327 , -0.43445647, 0.81112355, -1.177568 , 0.94679874,0.7710409 , -0.09612622, -0.85266286, -0.46487492, 1.0379548 ,1.0902969 , 0.21682492, -0.1771169 , 1.2194921 , 1.8131593 ,…]…

Learning

Model
Language: PHP
17
Target Vulnerability: CWE-89 SQL Injection

Function Call Traces<?php$conn = mysql_connect('localhost', 'mysql_user', 'mysql_password');mysql_select_db('dbname') ;$tainted = "";if ($_GET['input'] == "safe") {$tainted = mysql_real_escape_string($_GET['test']);} else {$tainted = $_GET['test'];}$query = "SELECT * FROM users where username = '" . $tainted . "'";
$res = mysql_query($query); //execution
mysql_close($conn);?>

Extract the called function name and the parametersin the symbolic execution
mysql_connect ( #str# , #str# , #str# )mysql_select_db ( #str# )mysql_real_escape_string ( _GET [ #str# ] )mysql_query ( #str# ' . mysql_real_escape_string ( _GET [ #str# ] ) . ' )mysql_query ( #str# ' . _GET [ #str# ] . ' )mysql_close ( mysql_connect ( #str# , #str# , #str# ) )18Classes / User Defined Functions
Expand the function call like making a Program Slice<?phpfunction Test($x) {if ($x < 10) {return 10;} else {return $x + $_GET['test'];}}$a = $_GET['test'] ? : 1;
$b = array(1, $_GET['test2'], 3);
if ($a == "test") {echo Test($b[0]);} else {echo Test($b[1]);}echo ( { #lnum# , #lnum# + _GET [ #str# ] } )echo ( { #lnum# , _GET [ #str# ] + _GET [ #str# ] } )19Filteringmysql_connect ( #str# , #str# , #str# )mysql_select_db ( #str# )mysql_real_escape_string ( _GET [ #str# ] )mysql_query ( #str# ' . mysql_real_escape_string ( _GET [ #str# ] ) . ' )mysql_query ( #str# ' . _GET [ #str# ] . ' )mysql_close ( mysql_connect ( #str# , #str# , #str# ) )mysql_query ( #str# ' . mysql_real_escape_string ( _GET [ #str# ] ) . ' )mysql_query ( #str# ' . _GET [ #str# ] . ' )Filter out traces other than mysql_query20Machine Learning Model
Input

LSTM

DenseOutput(Vulnerable or not)

LSTM
LSTM
LSTM

…

…

…

LSTM

21

Evaluation
22

Experiment (1)Objective
Confirm the impact of Word Embedding quality
Word Embedding Machine Learning Model
Algorithm(Same for all)

#Preprocess

Filtering1

Symbolic
Word2Vec
Execution Trace

LSTM + Dense + Sigmoid

Yes

2

Symbolic
Execution Trace

Word2Vec

LSTM + Dense + Sigmoid

No

3

Symbolic
Execution Trace

Bag of Words

LSTM + Dense + SigmoidNo4

token_get_all

Word2Vec

LSTM + Dense + Sigmoid

No5

token_get_all

Bag of Words

LSTM + Dense + Sigmoid

No23

Dataset
SARD* CWE-89 PHP Dataset
Safe samples

Unsafe samples

Total

8,640

912

9,552

SARD CWE-89 Dataset had an error in samples that use filter_var withFILTER_VALIDATE_EMAIL. The error was corrected.
* National Institute of Standards and Technology"The NIST Software Assurance Reference Dataset Project"https://samate.nist.gov/SARD/

24

Indicators• Receiver Operating Characteristic Curve(ROC Curve)– A graph that shows the characteristic of sensitivityof the model to the target vulnerability• Area Under the Curve (AUC)– Accumulated area under the curve25Result (1)26Comparison with TAP
Safe Samples

Unsafe Samples

Model
Precision Recall

F1

Precision Recall

F1

Accuracy

AUC

SymVuls

0.97780.99830.98790.97950.7851 0.8716

0.97790.9953TAP

0.97730.99880.98800.98740.7970 0.8820

0.9782

0.994127

Experiment (2)Objective
Confirm the versatility of the trained model• Prepared a set of very simple vulnerable PHP code
• Compare the loss#Content1

Very simple code2

filter_var + sprintf formatting

3Long code4

sprintf formatting28

Result (2)Evaluated with MSE (Mean Squared Error) - Lower is better

29

Summary30

RQ1
Would vulnerability detection result be
RQ1 improved if Symbolic Execution traces are usedfor Word Embedding?

• Yes, it does improve• Symbolic Execution helps the feature
extraction• Word Embedding quality is also an
important factor to keep the features
31

RQ2
Does the trained model have enough versatility
RQ2 to detect vulnerabilities in other test sourcecode?

• Low versatility if no filtering applied• The API that causes the vulnerability
needs to be specified in one way oranother32

EndThank you for listening
Any questions?
33