曝光台 注意防骗
网曝天猫店富美金盛家居专营店坑蒙拐骗欺诈消费者
respect to the refinement order. We can use the pointwise
extension of the narrowing of intervals to define a narrowing
operation over abstract heaps. We can then automate
this process, using the narrowing to enforce stabilization.
Automatic stabilization is not implemented in the current
version of CGS, the user must explicitly give the number of
refinement steps that shall be computed.
To illustrate this mechanism, consider for example a program
working on an array A of two pointers, a pointer variable
P and two integer variables I and J, and made of three
simple threads defined as follows:
void task1() { void task2() { void task3() {
A[0] = &I; P = A[0]; A[1] = &J;
} } }
Imagine that we are provided with a conservative field-insensitive
approximation H0 of the memory graph as follows:
H0 =
h&A, [−∞,+∞], [8, 8]i 7→ h&I, [−∞,+∞], [4, 4]i,
h&A, [−∞,+∞], [8, 8]i 7→ h&J, [−∞,+∞], [4, 4]i,
h&P, [−∞,+∞], [4, 4]i 7→ h&I, [−∞,+∞], [4, 4]i,
h&P, [−∞,+∞], [4, 4]i 7→ h&J, [−∞,+∞], [4, 4]i
assuming pointers and integers occupy four bytes in memory
on the architecture considered. After one step of iteration,
the elements at indices 0 and 1 of array A are entirely
determined, however the value of P is computed from the
points-to information contained in H0. Therefore we obtain
the following memory graph:
H1 =
h&A, [0, 0], [8, 8]i 7→ h&I, [0, 0], [4, 4]i,
h&A, [4, 4], [8, 8]i 7→ h&J, [0, 0], [4, 4]i,
h&P, [0, 0], [4, 4]i 7→ h&I, [−∞,+∞], [4, 4]i,
h&P, [0, 0], [4, 4]i 7→ h&J, [−∞,+∞], [4, 4]i
Note that the offset in the memory block &P has been solved
because the assignment P = A[0] writes its lefthand side at
the offset 0. After one more iteration step, the assignment
to P in task 2 can be precisely solved, since the memory
layout of A has been completely determined at the previous
iteration step. We finally obtain:
H2 =
h&A, [0, 0], [8, 8]i 7→ h&I, [0, 0], [4, 4]i,
h&A, [4, 4], [8, 8]i 7→ h&J, [0, 0], [4, 4]i,
h&P, [0, 0], [4, 4]i 7→ h&I, [0, 0], [4, 4]i
It now remains the problem of bootstrapping the iterative
process, i.e. obtaining the first approximation H0. We
first used Steensgaard’s analysis [24] enhanced with Das’
one-level flow edges optimization [13]. However the resulting
abstract heap was too coarse, and there were spurious
points-to relations introduced at that stage that remained
in all subsequent refinement steps. One source of imprecision
was due to the way message queues are allocated. The
unique malloc call that creates a queue is nested within
several function calls. Since in our memory model allocations
can only be distinguished by the syntactic location of
the corresponding malloc, all message queues were merged,
resulting in an unrecoverable loss of precision. Adding an
option to CGS allowing to inline the corresponding functions
solved this problem. The idea is to treat isolated sources of
imprecision manually in this way rather than complicating
the pointer analysis in order to cover all special cases. The
drawback is that this kind of instrumentation can only be
done by a high-end user who perfectly knows the internals
of the analysis and how to cope with this kind of situation
(see also [3] for a discussion of this issue).
A substantial amount of the remaining spurious points-to
relations was due to brutal unification operations in Steensgaard’s
analysis caused by pointers stored in global variables.
The solution consisted of extending Das analysis in
order to be able to handle n-level flow edges without sacrificing
efficiency. We believe that scalable versions of Andersen’s
analysis [2] could have been considered as well for
the bootstrap [18]. We unfortunately did not have the time
to implement an inclusion-based analysis and compare the
results.
This ends the presentation of the abstract interpretation
framework implemented in CGS. We now have to present
the details of the abstract semantic equations.
中国航空网 www.aero.cn
航空翻译 www.aviation.cn
本文链接地址：
航空资料36(59)
