曝光台 注意防骗
网曝天猫店富美金盛家居专营店坑蒙拐骗欺诈消费者
on abstract memory descriptions with …
cur
l
cur
l
cur
l
cur
l
cur
l
cur
l
Bor-Yuh Evan Chang - End-User Program Analysis
18
Outline
shape analyzer
abstract interpretation
splitting and
interpreting update
summarizing
type
inference
on checker
definitions
dll(h, p) =
if (h = null) then
true
else
h!prev = prev and
dll(h!next, h)
checkers
Bor-Yuh Evan Chang - End-User Program Analysis
Learn information
about the checker to
use it as an abstraction
1
2
C3ompare Compare and contrast
manual code review
and our automated
shape analysis
19
Overview: Split summaries
to interpret updates precisely
l
cur
l
cur
Bor-Yuh Evan Chang - End-User Program Analysis
Want abstract update to be “exact”, that is, to
update one “concrete memory cell”.
The example at a high-level: iterate using cur changing the
doubly-linked list from purple to red.
l
cur
split at cur
update cur purple to red
l
cur
Challenge:
How does the
analysis “split”
summaries and
know where to
“split”?
20
“Split forward”
by unfolding inductive definition
Ç
dll(h, p) =
if (h = null) then
true
else
h!prev = p and
dll(h!next, h)
Bor-Yuh Evan Chang - End-User Program Analysis
l
cur
get: cur!next
l
cur
null
p dll(cur, p)
l
cur
p
dll(n, cur)
n
Analysis doesn’t
forget the
empty case
21
“Split backward” also possible and necessary
dll(h, p) =
if (h = null) then
true
else
h!prev = p and
dll(h!next, h)
Bor-Yuh Evan Chang - End-User Program Analysis
l
cur
p
dll(n, cur)
n
for each node cur in list l {
remove cur if duplicate;
}
assert l is sorted,
doubly-linked with no
duplicates;
“dll segment”
l
cur
p0
dll(n, cur)
n
“dll segment”
cur!prev!next
= cur!next;
l
cur
dll(n, cur)
null n
get: cur!prev!next
Ç
Technical Details:
How does the analysis do this unfolding?
Why is this unfolding allowed?
(Key: Segments are also inductively defined)
[POPL’08]
How does the analysis know to do this unfolding?
22
Outline
shape analyzer
abstract interpretation
splitting and
interpreting update
summarizing
type
inference
on checker
definitions
Bor-Yuh Evan Chang - End-User Program Analysis
Contribution:
Turns testing
code into
specification for
static analysis
1
2
3
How do we
decide where to
unfold?
Derives additional
information to
guide unfolding
dll(h, p) =
if (h = null) then
true
else
h!prev = prev and
dll(h!next, h)
checkers
23
memory cell
(points-to:
°!next = ±)
Abstract memory as graphs
dll(h, p) =
if (h = null) then
true
else
h!prev = p and
dll(h!next, h)
Bor-Yuh Evan Chang - End-User Program Analysis
l
®
dll(null) dll(¯)
cur
°
dll(°)
¯
prev
next ±
Make endpoints and segments explicit, yet high-level
l dll(±, °)
±
“dll segment”
cur
°
®
sseeggmeenntt ssuummaarryy
checker
summary
(inductive pred)
memory
address (value)
Contribution: Generalization of checker
(Intuitively, dll(®,null) up to dll(°,¯).)
Some number of
memory cells
(thin edges)
Which summary (thick edge), in what
direction, and how far do we unfold to get
the edge ¯!next (cur!prev!next)?
¯
next
24
Types for deciding where to unfold
®
dll(null) dll(¯) dll(¯)
°
dll(®,null)
dll(¯,®)
dll(°,¯)
dll(±,°)
dll(null,±)
Checker “Run” (call tree/derivation)
Instance
Summary
null ® ¯ ° ± null
dll(h, p) =
if (h = null) then
true
else
h!prev = p and
dll(h!next, h)
中国航空网 www.aero.cn
航空翻译 www.aviation.cn
本文链接地址：
航空资料36(50)
