Filetype PDF | Posted on 04 Feb 2023 | 2 years ago
Authentication
digital resources
130x Filetype PDF File size 0.63 MB Source: www.usenix.org
SanRazoR: Reducing Redundant Sanitizer
Checks in C/C++ Programs
Jiang Zhang, University of Southern California; Shuai Wang, HKUST;
Manuel Rigger, Pinjia He, and Zhendong Su, ETH Zurich
https://www.usenix.org/conference/osdi21/presentation/zhang
This paper is included in the Proceedings of the
15th USENIX Symposium on Operating Systems
Design and Implementation.
July 14–16, 2021
978-1-939133-22-9
Open access to the Proceedings of the
15th USENIX Symposium on Operating
Systems Design and Implementation
is sponsored by USENIX.
SANRAZOR:ReducingRedundantSanitizerChecksinC/C++Programs
1 2∗ 3 3 3
Jiang Zhang Shuai Wang ManuelRigger Pingjia He ZhendongSu
1 2 3
University of Southern California HKUST ETHZurich
Abstract Sanitizers are commonly used by developers to find bugs
Sanitizers detect unsafe actions such as invalid memory ac- before software deployment. In principle, they could also be
cesses by inserting checks that are validated during a pro- used in deployed software, where they terminate program
gram’s execution. Despite their extensive use for debugging executions to prevent vulnerabilities from being exploited.
and vulnerability discovery, sanitizer checks often induce a In practice, however, the high runtime overhead of sanitizers
high runtime cost. One important reason for the high cost is, inhibits their adoption in this application scenario [33,40].
as we observe in this paper, that many sanitizer checks are For example, our study on SPEC CPU2006 benchmarks [34]
redundant — the same safety property is repeatedly checked shows that the geometric mean overheads induced by Ad-
—leadingtounnecessarily wasted computing resources. dressSanitizer (ASan) [32] and UndefinedBehaviorSanitizer
To help more profitably utilize sanitizers, we introduce (UBSan) [8] are, respectively, 73.8% and 160.1% (cf. Sec. 6).
SANRAZOR,apracticaltool aiming to effectively detect and It is difficult to reduce the overhead of sanitizer checks and
remove redundant sanitizer checks. SANRAZOR adopts a therefore accelerate the execution of sanitization-enabled pro-
novel hybrid approach — it captures both dynamic code cov- grams. To date, a number of approaches have been proposed
erage and static data dependencies of checks, and uses the aiming at finding unnecessary sanitizer checks with static
extracted information to perform a redundant check analysis. analysis [6,9,11,12,15,25,37,39,44,45]. For example, some
Ourevaluation on the SPEC benchmarks shows that SANRA- approaches remove array bound checks by checking whether
ZORcanreducetheoverhead of sanitizers significantly, from the value range of an index falls within the array size. They
73.8%to28.0–62.0%for AddressSanitizer, and from 160.1% usually perform heavyweight, specialized program analyses
to 36.6–124.4% for UndefinedBehaviorSanitizer (depending to reduce specific sanitizer checks. In contrast, ASAP [40],
onthe applied reduction scheme). Our further evaluation on the most closely related work to ours, elides sanitizer checks
38 CVEsfrom10commonly-usedprogramsshowsthat SAN- deemedthe most costly based on a user-provided overhead
RAZOR-reduced checks suffice to detect at least 33 out of budget. Despite being general and supporting sanitizers of dif-
the 38 CVEs. Furthermore, by combining SANRAZOR with ferent implementations, ASAP removes checks irrespective
an existing sanitizer reduction tool ASAP, we show synergis- of their importance and may overoptimisitcally remove them,
tic effect by reducing the runtime cost to only 7.0% with a resulting in missed vulnerabilities. Thus, prior approaches for
reasonable tradeoff of security. reducing sanitizer checks use either sanitizer-specific static
analyses (e.g., [9,37]) to remove only semantically redundant
1 Introduction checks, or general heuristics [40] to remove costly sanitizer
checks irrespective of their semantics.
Software sanitizers are designed to detect software bugs This work explores a new, novel design point — it intro-
and vulnerabilities in code written in unsafe languages like duces a general framework, SANRAZOR, for effectively re-
C/C++ [33]. A sanitizer typically inserts additional checks movinglikely redundant checks. SANRAZOR is designed as
into the program during compilation; at run time, the sani- a hybrid approach. First, it gathers coverage statistics during
tizer check terminates the program if it detects unsafe actions a profiling phase (e.g., based on a program’s test suite). It
or states (e.g., a buffer overflow). To date, various sanitizers then performs a correlation analysis, employing both the pro-
have been designed to help detect vulnerabilities in C/C++ filed coverage patterns as well as static data dependencies,
programs [4,8,24,32,35]. to pinpoint and remove checks identified as likely redundant.
Like ASAP [40], SANRAZOR is general and orthogonal to
∗Corresponding author. existing sanitizer reduction approaches that focus on specific
USENIX Association 15th USENIX Symposium on Operating Systems Design and Implementation 479
sanitizer check implementations [9, 37, 44]. Distinct from ASan. Memory access errors like buffer overflow and use-
ASAP,SANRAZORidentifiesandremovessanitizerchecks after-free are severe vulnerabilities in C/C++ programs. ASan
that repeatedly checkthesameprogramproperty,whileASAP is designed to detect memory errors [32], and consists of an
removes sanitizer checks of high cost and may miss vulnera- instrumentation module and a runtime library. The instru-
bilities. Although, like ASAP, SANRAZOR is unsound, i.e., it mentation module allocates shadow memory regions for each
mayremovechecksevenwhentheyareunique,inpractice, memoryaddressusedbytheprogram.Italsoinstrumentseach
our evaluation results show that it accurately maintains the memoryloadandstoreoperation such that before a memory
sanitizer’s effectiveness in discovering defects and provides address a is used to access memory, a will be mapped to its
significantly reduced runtime overhead. corresponding shadow memory address sa; the value stored
Weevaluate the performance gain of SANRAZOR on the in sa is then loaded and checked to decide whether the access
SPECCPU2006benchmark.Theresultsshowthat SANRA- via a is safe. The instrumentation module also allocates a
ZOR reduces geometric mean runtime overhead caused by “bad” region for each shadow memory region; directly using
ASan from 73.8% to 28.0–62.0% (depending on the differ- a shadow memory address sa in the application code will be
ent reduction schemes in SANRAZOR). Similarly, geometric redirected to the “bad” region, which is inaccessible via page
meanoverheadincurred by UBSan on SPEC programs is re- protection. The runtime library hooks the malloc function
ducedfrom160.1%to36.6–124.4%.Tomeasuretheaccuracy to create poisoned “redzones” next to allocated memories to
of SANRAZOR,weevaluate10popularprogramswithatotal detect memory access errors. Similarly, the free function is
of 38 known CVEs. Results show that after removing redun- instrumented to put the entire deallocated memory region into
dant sanitizer checks, at least 33 CVEs can still be discovered. “redzones.” This ensures that the recently-freed region will
ComparedwithASAP,SANRAZORsignificantlyoutperforms not be used by malloc for reallocation.
ASAPbydiscoveringmoreCVEswhenachievingthesame UBSan.Undefinedbehaviorscanincurseveresoftware vul-
amountofcostreduction. We also explored practical methods nerabilities [41]. UBSan [8] detects a large set of common
to combine SANRAZOR and ASAPandreduceruntimecost undefined behaviors in C/C++ code, such as out-of-bounds
to only 7.0% with a reasonable tradeoff of security. These access, divided by zero, and invalid shift. We briefly introduce
promising results suggest that SANRAZOR could help pro- one undefined behavior that UBSan can detect:
motetheadoption of sanitizers in production usage. In sum, Out-of-bounds Array Access Unlike ASan, which relies on
wemakethefollowingmaincontributions: shadowmemory,UBSandetectsout-of-boundsarrayaccesses
• Attheconceptual level, we introduce the novel approach by comparing each array index with the array size. Consider
to reducing performance overhead incurred by sanitizers the sample code below:
byidentifying and removing likely redundant checks. By 1 UChar buf[32]; // buf size is 32
reducing sanitizer cost, sanitization-enabled programs can 2 for(i = 0; i < nBuf; i++)
be executed faster, making sanitizer adoption in production 3 out[i] = buf[nBuf-i-1];
use more practical.
• Atthetechnical level, we design and implement a practical where buf has 32 elements. When nBuf is greater than 32,
tool, SANRAZOR, to reduce sanitizer checks. SANRAZOR executing buf[nBuf-i-1] may trigger an out-of-bounds ac-
performs a hybrid analysis by leveraging both coverage cess (e.g. when i is 0). UBSan identifies this by placing an
patterns and static data dependency features to identify extra if condition to compare the array index nBuf-i-1 with
sanitizer checks as likely redundant. the array size 32 before executing the loop body.
• Atthe empirical level, our evaluation on the SPEC bench- 3 ProblemFormulation
marks shows that SANRAZOR can significantly reduce
runtime overhead caused by ASan and UBSan. Moreover, Conceptually, a sanitizer check c(v) (v is the input parameter)
our evaluation on real-world software with known CVEs can be defined as follows:
shows that after applying SANRAZOR to reduce sanitizer
checks, almost all CVEs can still be discovered. if(P(v) does not hold) abort_or_alert();
We have publicly released SANRAZOR on GitHub at where c checks whether a property P holds w.r.t. parameter
https://github.com/SanRazor-repo/SanRazor. v. Usually, v denotes critical program information (e.g., code
2 Preliminaries pointers), and by violating property P, e.g., a null pointer
dereference, c either aborts program execution or alerts the
Sanitizers are dynamic tools for finding software defects [33]. user. Considering a program p with N sanitizer checks in-
Sanitizers insert sanitizer checks, which are statements for serted, we use ci.v and ci.P to denote the parameter of the ith
monitoring program behaviors and validating whether they check ci and its checked property throughout this section.
violate certain properties. We now introduce two sanitizers AsintroducedinSec.2,computationoverheadcanbeintro-
provided by the LLVM framework, ASan and UBSan, which duced by each c , since c performs complex safety property
i i
have helped to detect many vulnerabilities [33]. checking, and may require extra memory to store metadata.
480 15th USENIX Symposium on Operating Systems Design and Implementation USENIX Association
Workload
Instrumented SanRazor
t Instrument each LLVM IR Profile instrumented
Lis
eck identified check code
LLVM IR Identify Ch Dynamic LLVM IRwith
with sanitizer checks Che Static Patterns Redundant reduced sanitizer
checks ck Constructdata Patterns Check redundancy Check List Check checks
Lis
t dependencygraph analysis reduction
Figure 1: Workflow of SANRAZOR.
Nevertheless, a large portion of sanitizer checks repeatedly as- still be detected, either by another sanitizer check cj or by a
sert identical properties, thus wasting computing resources on user-defined check, then c is a redundant sanitizer check.
i
properties deemed safe. We aim to remove redundant checks Moreformally, given a nontrivial, single-threaded program
to reduce cost, thus making the production adoption of san- pwithasetofchecksc∈C,twochecksc andc aredeemed
itizer checks more practically feasible. Next, we present a i j
motivating example, and then formulate the notion of “redun- identical, when the following condition holds:
dant sanitizer checks” from a functionality perspective. (c ∈dom(c )∨c ∈dom(c))∧[[c.v]]=[[c .v]]∧c .P=c .P
i j j i i j i j
wherec ∈dom(c )andc ∈dom(c)denotethatc dominates
3.1 SampleRedundantChecksinbzip2 i j j i i
cj in the control flow graph or vice versa. Therefore, every
Weshowanexampleofchecksinbzip2thatrepeatedlyvali- execution from the program entry point to cj goes through
date the same array index as follows: ci or vice versa [5]. [[ci.v]] = [[cj.v]] represents that ci.v and
c .v are semantically equivalent. c .P = c .P means that c
for(i=0; i < nblock; i++) { j i j i
j = eclass8[i]; //ASan1 and cj are the same kind of checks (e.g., they are both ASan
k = ftab[j] - 1; //ASan2; checks, which can be recognized with pattern matching; cf.
ftab[j] = k; //ASan3; ASan2 and ASan3 identical? Sec. 4.1). When ci and cj satisfy the given condition and
fmap[k] = i; //ASan4; k < fmap_size always hold? ci ∈ dom(cj), cj can be removed because if cj is executed,
WhenASanisenabled,foursanitizer checks are inserted ci must be executed and they check the same property. The
to detect out-of-bound array access. Existing research could given condition specifies the functional equivalence of ci and
remove ASan4, by asserting k always falls within the size cj. However, computability theory (e.g., Rice’s theorem [29])
of fmap. In contrast, SANRAZOR advocates a new and or- suggests that it could be very difficult, if possible at all, to
assert [[c .v]] = [[c .v]] for nontrivial programs. Moreover, per-
thogonal focus by deciding that ASan2 and ASan3 validate i j
the same index, and therefore, ASan3 can be removed without forming control flow analysis to recover the dominator tree
1 (e.g., dom(cj)) information can be challenging and lead to
missingpotential defects. Indeed,ourstudy shows that check false alarms, especially for cases where points-to analyses are
redundancy is a general concern in real-world software (see extensively used in performing control flow analysis.
Sec. 6), motivating a strong need for optimization. Also, to Given the theoretical challenge of identifying redundant
the best of our knowledge, standard compiler optimizations sanitizer checks, we instead propose a practical approxima-
andpreviousresearchinthisfield(e.g.,[6,9,11,12,15,28]) do tion to identify likely redundant checks. Our approximation
notstrive to use “similarity analysis” to reveal the equalivance extracts both code coverage patterns and static input depen-
of ASan2 and ASan3 and shave ASan3 accordingly. In fact, dency patterns of checks (cf. Sec. 4); two checks are deemed
our study shows that, when full optimizations (-O3) of clang “redundant” when they yield identical dynamic and static pat-
are enabled, no sanitizers can be shaved for this case. This terns. Specifically, we search for a pair of checks ci and cj and
observation underlies the key novelty of SANRAZOR, whose flagthemasredundantif all the following conditions hold:
design will be introduced in Sec. 4. • c and c have correlated dynamic code coverage patterns,
i j
whenexecuting the software with a nontrivial amount of
3.2 RedundantSanitizer Checks workload inputs. Here, coverage patterns are checked re-
garding their “correlation”, such that they can be identical,
Westart by giving a general definition of what a redundant or one check’s coverage pattern can subsume the other’s
check is, before refining the notion in an operational way: pattern (see Sec. 4.4 for details).
• c .P(c .v) andc .P(c .v) are approximately equivalentw.r.t.
Definition 1. Assume that a sanitizer check c that could i i j j
i static data dependency patterns deduced by our technique:
detect a hypothetical bug B in program p is removed. If B can [[c .P(c .v)]] ≈ [[c .P(c .v)]].
i i j j
1WescopeSANRAZORtosinglethreadedprograms.SeeSec.4forfurther The first condition can be determined by instrumenting
discussion of application scope. and profiling the program, and for the second, we assert
USENIX Association 15th USENIX Symposium on Operating Systems Design and Implementation 481
no reviews yet
Please Login to review.
