, or
( int GUARDED BY(mu))[10]. If attributes could be attached
to types, PT GUARDED BY would be unnecessary.
Attaching attributes to types would result in a better and
more accurate analysis. However, it was deemed infeasible
for C++ because it would require invasive changes to the C++
type system that could potentially affect core C++ semantics
in subtle ways, such as template instantiation and function
overloading.
No dependent type parameters. Race-free type systems as
described in the literature often allow classes to be parameterized
by the objects that are responsible for controlling access.
[11] [3] For example, assume a Graph class has a list of nodes,
and a single mutex that protects all of them. In this case, theNode class should technically be parameterized by the graph
object that guards it (similar to inner classes in Java), but that
relationship cannot be easily expressed with attributes.
No alias analysis. C++ programs typically make heavy use
of pointer aliasing; we currently lack an alias analysis. This
can occasionally cause false positives, such as when a program
locks a mutex using one alias, but the GUARDED BY attribute
refers to the same mutex using a different alias.
VI. EXPERIMENTAL RESULTS AND CONCLUSION
Clang thread safety analysis is currently deployed on a wide
scale at Google. The analysis is turned on by default, across
the company, for every C++ build. Over 20,000 C++ files
are currently annotated, with more than 140,000 annotations,
and those numbers are increasing every day. The annotated
code spans a wide range of projects, including many of
Google’s core services. Use of the annotations at Google is
entirely voluntary, so the high level of adoption suggests that
engineering teams at Google have found the annotations to be
useful.
Because race conditions are insidious, Google uses both
static analysis and dynamic analysis tools such as Thread
Sanitizer [12]. We have found that these tools complement
each other. Dynamic analysis operates without annotations and
thus can be applied more widely. However, dynamic analysis
can only detect race conditions in the subset of program
executions that occur in test code. As a result, effective
dynamic analysis requires good test coverage, and cannot
report potential bugs until test time. Static analysis is less
flexible, but covers all possible program executions; it also
reports errors earlier, at compile time.
Although the need for handwritten annotations may appear
to be a disadvantage, we have found that the annotations
confer significant benefits with respect to software evolution
and maintenance. Thread safety annotations are widely used
in Google’s core libraries and APIs. Annotating libraries has
proven to be particularly important, because the annotations
serve as a form of machine-checked documentation. The
developers of a library and the clients of that library are usually
different engineering teams. As a result, the client teams often
do not fully understand the locking protocol employed by the
library. Other documentation is usually out of date or nonexistent,
so it is easy to make mistakes. By using annotations,
the locking protocol becomes part of the published API, and
the compiler will warn about incorrect usage.
Annotations have also proven useful for enforcing internal
design constraints as software evolves over time. For example,
the initial design of a thread-safe class must establish certain
constraints: locks are used in a particular way to protect
private data. Over time, however, that class will be read
and modified by many different engineers. Not only may
the initial constraints be forgotten, they may change when
code is refactored. When examining change logs, we found
several cases in which an engineer added a new method to a
class, forgot to acquire the appropriate locks, and consequently
had to debug the resulting race condition by hand. When
the constraints are explicitly specified with annotations, the
compiler can prevent such bugs by mechanically checking new
code for consistency with existing annotations.
The use of annotations does entail costs beyond the effort
required to write the annotations. In particular, we have found
that about 50% of the warnings produced by the analysis are
caused not by incorrect code but rather by incorrect or missing
annotations, such as failure to put a REQUIRES attribute
on getter and setter methods. Thread safety annotations are
roughly analogous to the C++ const qualifier in this regard.
Whether such warnings are false positives depends on
your point of view. Google’s philosophy is that incorrect
annotations are “bugs in the documentation.” Because APIs
are read many times by many engineers, it is important that
the public interfaces be accurately documented.
Excluding cases in which the annotations were clearly
wrong, the false positive rate is otherwise quite low: less than
5%. Most false positives are caused by either (a) pointer aliasing,
(b) conditionally acquired mutexes, or (c) initialization
code that does not need to acquire a mutex.
Conclusion
Type systems for thread safety have previously been implemented
for other languages, most notably Java [3] [11].
Clang thread safety analysis brings the benefit of such systems
to C++. The analysis has been implemented in a production
C++ compiler, tested in a production environment, and adopted
internally by one of the world’s largest software companies.
REFERENCES
[1] K. Asanovic et al., “A view of the parallel computing landscape,”
Communications of the ACM, vol. 52, no. 10, 2009.
[2] L.-C. Wu, “C/C++ thread safety annotations,” 2008. [Online]. Available:
https://docs.google.com/a/google.com/document/d/1 d9MvYX3LpjTk
3nlubM5LE4dFmU91SDabVdWp9-VDxc
[3] M. Abadi, C. Flanagan, and S. N. Freund, “Types for safe locking: Static
race detection for java,” ACM Transactions on Programming Languages
and Systems, vol. 28, no. 2, 2006.
[4] “Clang thread safety analysis documentation.” [Online]. Available:
http://clang.llvm.org/docs/ThreadSafetyAnalysis.html
[5] “Clang: A c-language front-end for llvm.” [Online]. Available:
http://clang.llvm.org
[6] D. F. Sutherland and W. L. Scherlis, “Composable thread coloring,”
PPoPP ’10: Proceedings of the ACM Symposium on Principles and
Practice of Parallel Programming, 2010.
[7] K. Crary, D. Walker, and G. Morrisett, “Typed memory management in
a calculus of capabilities,” Proceedings of POPL, 1999.
[8] J. Boyland, J. Noble, and W. Retert, “Capabilities for sharing,” Proceedings
of ECOOP, 2001.
[9] J.-Y. Girard, “Linear logic,” Theoretical computer science, vol. 50, no. 1,
pp. 1–101, 1987.
[10] S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson,
“Eraser: A dynamic data race detector for multithreaded programs.”
ACM Transactions on Computer Systems (TOCS), vol. 15, no. 4, 1997.
[11] C. Boyapati and M. Rinard, “A parameterized type system for race-free
Java programs,” Proceedings of OOPSLA, 2001.
[12] K. Serebryany and T. Iskhodzhanov, “Threadsanitizer: data race detection
in practice,” Workshop on Binary Instrumentation and Applications,
2009.
An Optimized Template Matching Approach to Intra Coding
in Video/Image Compression
Hui Su, Jingning Han, and Yaowu Xu
Chrome Media, Google Inc., 1950 Charleston Road, Mountain View, CA 94043
ABSTRACT
The template matching prediction is an established approach to intra-frame coding that makes use of previously
coded pixels in the same frame for reference. It compares the previously reconstructed upper and left boundaries
in searching from the reference area the best matched block for prediction, and hence eliminates the need of
sending additional information to reproduce the same prediction at decoder. In viewing the image signal as an
auto-regressive model, this work is premised on the fact that pixels closer to the known block boundary are better
predicted than those far apart. It significantly extends the scope of the template matching approach, which is
typically followed by a conventional discrete cosine transform (DCT) for the prediction residuals, by employing an
asymmetric discrete sine transform (ADST), whose basis functions vanish at the prediction boundary and reach
maximum magnitude at far end, to fully exploit statistics of the residual signals. It was experimentally shown
that the proposed scheme provides substantial coding performance gains on top of the conventional template
matching method over the baseline.
Keywords: Template matching, Intra prediction, Transform coding, Asymmetric discrete sine transform
1. INTRODUCTION
Intra-frame coding is a key component in video/image compression system. It predicts from previously reconstructed
neighboring pixels to largely remove spatial redundancies. A codec typically allows various prediction
directions1–3 , and the encoder selects the one that best describes the texture patterns (and hence rendering
minimal rate-distortion cost) for block coding. Such boundary extrapolation based prediction is efficient when
the image signals are well modeled by a first-order Markovian process. In practice, however, image signals might
contain certain complicated patterns repeatedly appearing, which the boundary prediction approach can not
effectively capture. This motivates the initial block matching prediction, that searches in the previously reconstructed
frame area for reference, as an additional mode.4 A displacement vector per block is hence needed to
inform decoder to reproduce the prediction, akin the motion vector for inter-frame motion compensation. To
overcome such overhead cost that diminishes the performance gains, a template matching prediction (TMP)
approach was developed5
that employs the available neighboring pixels of a block as a template, measures the
template similarity between the block of interest and the candidate references, and chooses the most “similar” one
as the prediction. Clearly the decoder is able to repeat the same process without recourse to further information,
which further allows the TMP to operate in smaller block size for more precise prediction at no additional cost.
A conventional 2D-DCT is then applied to the prediction residuals, followed by quantization and entropy coding,
to encode the block. Certain coding performance gains were obtained by integrating the TMP in a regular intra
coder.
In viewing the image signals as an auto-regressive process, pixels close to the block boundaries are more
correlated to the template pixels, and hence are better predicted by the matched reference, than those sitting
at far end. Therefore, the residuals ought to exhibit smaller variance at the known boundaries and gradually
increased energy to the opposite end, which makes the efficacy of the use of DCT questionable due to the fact that
its basis functions get to the maximal magnitude at both ends and are agnostic to the statistical characteristics
of the residuals. This work addresses this issue by incorporating the ADST,6, 7 whose basis functions possess
the desired asymmetric properties, as an alternative to the TMP residuals for optimal coding performance. A
complementary similarity measurement based on weighted template matching, in recognition of the statistical
E-mails: {huisu, jingning, yaowu}@google.com.
Visual Information Processing and Communication V, edited by Amir Said, Onur G. Guleryuz,
Robert L. Stevenson, Proc. of SPIE-IS&T Electronic Imaging, SPIE Vol. 9029, 902904
© 2014 SPIE-IS&T · CCC code: 0277-786X/14/$18 · doi: 10.1117/12.2040890
SPIE-IS&T/ Vol. 9029 902904-1
Downloaded From: http://proceedings.spiedigitallibrary.org/ on 01/05/2015 Terms of Use: http://spiedl.org/termsReconstructed Pixels
To-be-coded Pixels
Target
Block
Prediction
Block
Target Template
Candidate Template
Figure 1. Template matching intra prediction.
variations across the block, was also proposed to improve the search quality. The scheme was implemented in
the VP9 framework, in conjunction with other boundary prediction based intra coding modes. Experiments
demonstrated remarkable performance advantages over conventional TMP as well as the baseline codec.
The rest of the paper is organized as follows: Sec. 2 presents a brief review on the template matching
approach. In Sec. 3, we describe the proposed techniques in details. Experimenting results are presented in Sec.
4, and Sec. 5 concludes the paper.
2. REVISITING MATCHING PREDICTION
We provide a brief review on the TMP approach5
in this section. As shown in Fig. 1, the TMP employs the
pixels in the adjacent upper rows and left columns of a block as its template. Every template in the reconstructed
area of the frame is considered as a reference template, and the template of the block to be encoded is the target
template. The similarity between the target template and the reference templates is then evaluated in terms
of sum of absolute/squared difference. The encoder selects amongst the reference templates the one that best
resembles the target template as the candidate template, and the block corresponding to this candidate template
is used as the prediction for the target block. Since it only involves comparing reconstructed pixels, the same
operations can be repeated at the decoder side without any additional side information sent, resulting in higher
compression efficiency than the direct block matching approach.4 As a consequence, the decoding process gets
more computationally loaded.
The TMP approach was shown to be particularly efficient in the scenarios where certain complicated texture
patterns, that cannot be captured by the conventional directional intra prediction modes, appear repeatedly in the
image/frame. Recent research efforts have been devoted to further improve the TMP scheme, including combining
multiple candidates with top similarity scores,8 using hybrid TMP and block matching (with displacement vector
sent explicitly),9
etc. This work is focused on optimizing the original TMP approach by observing and exploiting
the statistical property of the TMP residual signals. It is noteworthy that the proposed principles are generally
applicable to other advanced variants as well.
3. PROPOSED TECHNIQUES
We view the image signals as an auto-regressive model, which implies that two nearby pixels are more correlated
than those far apart. Since the template of a matched reference block closely resembles that of the block of
TEMPLATE
SPIE-IS&T/ Vol. 9029 902904-2
Downloaded From: http://proceedings.spiedigitallibrary.org/ on 01/05/2015 Terms of Use: http://spiedl.org/termsTarget Block Pixels
Template Pixels with
Larger Weight
Template Pixels with
Smaller Weight
Figure 2. The proposed weighted template matching scheme. The pixels that are closer to the target block are assigned
with larger weight.
interest, the pixels sitting close to the known boundaries of the two blocks are element-wisely more correlated,
than those at the opposite end. Hence the pixels near the top/left boundaries are better predicted by the matched
reference block, which translates into a key observation that the variance of prediction residuals tends to vanish
at the known boundaries and gradually increase towards the far end. This inspires that unlike the discrete
cosine transform (DCT) whose basis functions get maximum magnitude at both ends, the (near) optimal spatial
transform for the TMP residuals should possess such asymmetric properties. We hence propose to employ the
asymmetric discrete sine transform (ADST)6, 7 for transform coding of the TMP residuals. A complementary
matching approach that expands the template to multiple boundary rows and columns, and uses a weighted
sum of difference measurement is first developed for more precise referencing. A statistical study of the TMP
residuals, followed by the detailed discussion of ADST will be provided next.
3.1 Weighted Template Matching
In order to obtain reliable template matching, it is reasonable to define multiple layers of boundary pixels
as the template of a block. In our study, we have observed that the prediction accuracy can be improved
when the number of rows and columns in the template increases. However, it is not wise to adopt too many
layers, as the gain in matching accuracy becomes saturated and the computational complexity explodes. In our
implementation, the template consists of the pixels in the 2 rows and 2 columns above and to the left of the
given block, which gives a good tradeoff between accuracy and computation complexity.
The similarity between the target templates and reference templates can be measured by the sum of absolute
difference (SAD). Along the line of recognizing the variations in statistics, the template pixels closer to the block
are highly correlated to the block content, and hence should be more weighted in the SAD calculation than those
distant ones. This idea is illustrated in Fig. 2. A weight ratio of 3:2 for the inner row/column versus the outer
row/column is used in this work.
3.2 Spatial Transformation
In video/image compression, the prediction residuals are typically processed via transformation to further remove
the remaining spatial redundancy, before the quantization and entropy coding modules. The Karhunen-Loeve
transform (KLT) is considered as the optimal spatial transform in terms of energy compaction. However, KLT
SPIE-IS&T/ Vol. 9029 902904-3
Downloaded From: http://proceedings.spiedigitallibrary.org/ on 01/05/2015 Terms of Use: http://spiedl.org/termsis rarely used in practical coding system due to its high computation complexity. The DCT has long been a
popular substitute due to its good tradeoff between energy compaction and complexity. The basis functions of
the DCT are as follows:
[TC ]j,i =
α cos
π(j − 1)(2i − 1)
2N
, (1)
where N is the block size, i, j ∈ {1, 2, · · · , N} denote the space and frequency indexes, respectively; and
α =
q
1
N
, if j = 1
q
2
N
, otherwise
It is easy to see that the basis functions of the DCT achieve their maximum energy at both ends (i.e., i = 1 or
i = N).
Assuming the template of a matched reference block closely approximates that of the block of interest, it is
highly likely that pixels close to these known boundaries are also well predicted, while those distant pixels are
less correlated, which results in a relatively higher residual variance. This postulation is verified by the following
experimental study. We collected the absolute values of the TMP prediction residues element-wisely over 8000
blocks (of dimension 4 × 4) from the foreman sequence, and the average of the residue signal at each pixel
location was calculated, as shown below:
4.05 4.37 4.51 5.13
4.72 5.48 5.50 6.60
5.04 5.95 6.12 7.32
5.50 6.28 6.97 8.20
As can be seen from the matrix, the variance of the prediction residue signal indeed increases along both the
horizontal and vertical directions.
As abovementioned, the basis functions of the conventional DCT achieve their maximum energy at both ends
and are therefore agnostic to the statistical patterns of the prediction residuals. As an alternative, the ADST6, 7
has basis functions of form:
[TS]j,i =
2
√
2N + 1
sin
(2j − 1)iπ
2N + 1
, (2)
where N is the block size, i, j ∈ {1, 2, · · · , N} denote the space and frequency indexes, respectively. It is
shown6, 7 that the ADST is a better approximation of the optimal KLT than the DCT when the partial boundary
information is available. Clearly, the basis functions of ADST vanishes at the known prediction boundary
(i = 1) and maximizes at the far end (i = N), and therefore matches well with the statistical patterns of the
TMP residuals. We hence propose to employ the ADST as the spatial transform for the TMP residuals. It is
experimentally shown in the next section that the use of ADST provides substantial performance improvement
over the TMP followed by the conventional DCT.
4. EXPERIMENT RESULTS
The proposed scheme was tested in the VP9 framework.1 We verified its efficacy in a relatively simplified setting,
where the block size was fixed as 8 × 8. There are 10 intra prediction modes in VP9, including vertical prediction,
horizontal prediction, 8 angular prediction modes, and a “true motion” mode that utilizes the left, above and
corner pixels simultaneously. The TMP scheme was implemented as an additional mode to the 10 existing ones.
The selection among the 11 modes is based on rate-distortion optimization. In the TMP mode, the 8 × 8 block
is further partitioned into four 4 × 4 blocks, each of which is predicted via template matching, followed by the
2D-ADST transform, quantization, and reconstruction, in a raster scan order. The template consists of pixels
from 2 rows and 2 columns above and to the left of the given block. For the weighted template matching, we
use a weight ratio 3:2 for the inner row/column versus the outer row/column, as shown in Fig. 2.
SPIE-IS&T/ Vol. 9029 902904-4
Downloaded From: http://proceedings.spiedigitallibrary.org/ on 01/05/2015 Terms of Use: http://spiedl.org/terms2 3 4 5 6
x 104
36
37
38
39
40
41
42
43
44
Bits per frame
PSNR
VP9 Baseline
Template Matching
Proposed Scheme
5 6 7 8 9 10 11 12
x 104
36
37
38
39
40
41
42
Bits per frame
PSNR
VP9 Baseline
Template Matching
Proposed Scheme
Figure 3. Rate-Distortion curves of the Ice (upper) and Foreman (lower) test sequences.
Several test video clips were used to compare the coding efficiency, including the Ice, Foreman, and Carphone
sequence. For every test sequence, the first 75 frames were coded as key-frame (i.e., all blocks were coded in intra
modes), at various bit-rates. The coding performance gains of the conventional TMP and the proposed method
over the reference codec, measured by the Bjontegaard metric, are shown in Table 1. Clearly, the proposed
approach that optimizes the transformation for prediction residual significantly improves the performance of
TMP, and both outperform the reference VP9 baseline. The rate-distortion curves of the ice and foreman
sequence are also provided in Fig. 3. It can be seen from the figure that the proposed techniques boost the
coding efficiency of the conventional TMP consistently.
5. CONCLUSIONS AND FUTURE WORK
This work proposed a novel approach that incorporated the ADST for TMP prediction residuals as an additional
mode for intra-frame coding. A complementary template matching method along the lines of recognizing the
SPIE-IS&T/ Vol. 9029 902904-5
Downloaded From: http://proceedings.spiedigitallibrary.org/ on 01/05/2015 Terms of Use: http://spiedl.org/termsTable 1. Coding performance gains over VP9 baseline in terms of bit-rate reduction percentage.
Sequences Conventional TMP Proposed Method
Ice 2.89 3.78
Foreman 2.88 3.33
Carphone 1.05 1.35
statistical variations across block was also provided for more precise reference search. The scheme implemented
in the VP9 framework demonstrated substantial performance improvements over the conventional TMP as well
as the reference codec.
The TMP approach can also be applied to inter-frame prediction.10 The template of a block is defined as
the pixels in the adjacent upper rows and left columns, in the same way as in the case of intra prediction.
The optimal template which is best matched to that of the block of interest is found in a previously encoded
reference frame, and the block to be encoded is filled in by copying the block corresponding the optimal template.
By the same principles in this work, the residue signal of the template matching inter prediction should also
present asymmetric statistical property across the block. We thus expect the ADST to be more efficient than the
conventional DCT for the transform coding of the template matching inter prediction, and are currently working
along this direction.
REFERENCES
[1] VP9 Video Codec , http://www.webmproject.org/vp9/.
[2] Wiegand, T., Sullivan, G. J., Bjontegaard, G., and Luthra, A., “Overview of the H.264/avc video coding
standard,” IEEE Trans. Circuits and Systems for Video Technology 13, 560–576 (July 2003).
[3] Sullivan, G., J. Ohm, W. H., and Wiegand, T., “Overview of the high effciency video coding (HEVC)
standard,” IEEE Trans. Circuits and Systems for Video Technology 22, 1649–1668 (Dec. 2012).
[4] Yu, S. and Chrysafis, C., “New intra prediction using intra-macroblock motion compensation,” Tech. Rep.
JVT-C151 (2002).
[5] Tan, T., Boon, C., and Suzuki, Y., “Intra prediction by template matching,” IEEE Proc. ICIP , 1693–1696
(2006).
[6] Han, J., Saxena, A., and Rose, K., “Towards jointly optimal spatial prediction and adaptive transform in
video/image coding,” IEEE Proc. ICASSP , 726–729 (2010).
[7] Han, J., Saxena, A., Melkote, V., and Rose, K., “Jointly optimized spatial prediction and block transform
for video and image coding,” IEEE Trans. on Image Processing 21, 1874–1884 (2012).
[8] Tan, T., Boon, C., and Suzuki, Y., “Intra prediction by averaged template matching predictors,” IEEE
Proc. CCNC (2007).
[9] Cherigui, S., Thoreau, D., Guillotel, P., and Perez, P., “Hybrid template and block matching algorithm for
image intra prediction,” IEEE Proc. ICASSP , 781–784 (2012).
[10] Sugimoto, K., Kobayashi, M., Suzuki, Y., Kato, S., and Boon, C. S., “Inter frame coding with template
matching spatio-temporal prediction,” IEEE Proc. ICIP (2004).
SPIE-IS&T/ Vol. 9029 902904-6
Downloaded From: http://proceedings.spiedigitallibrary.org/ on 01/05/2015 Terms of Use: http://spiedl.org/terms
How Many People Visit YouTube? Imputing
Missing Events in Panels With Excess Zeros
Georg M. Goerg, Yuxue Jin, Nicolas Remy, Jim Koehler1
1 Google, Inc.; United States
E-mail for correspondence: gmg@google.com
Abstract: Media-metering panels track TV and online usage of people to analyze
viewing behavior. However, panel data is often incomplete due to nonregistered
devices, non-compliant panelists, or work usage. We thus propose a
probabilistic model to impute missing events in data with excess zeros using
a negative-binomial hurdle model for the unobserved events and beta-binomial
sub-sampling to account for missingness. We then use the presented models to
estimate the number of people in Germany who visit YouTube.
Keywords: imputation; missing data; zero inflation; panel data.
1 Introduction
Media panels (GfK Consumer Panels, 2013) are used by advertisers to
estimate reach and frequency of a campaign: reach is the fraction of the
population that has seen an ad, frequency tells us how often they have seen
it (on average). It is important to get good estimates from panel data, as
they largely determine the cost of an ad spot on TV or a website.
Na¨ıvely, one would use a sample fraction of the number of non-zero events
(website visits, TV spots watched, etc.) per unit time to estimate reach;
similarly, for frequency. This, however, suffers from underestimation as panels
often only record a fraction of all events due to e.g., non-compliance or
work usage. Correcting this bias and imputing missing events has been
studied previously (Fader and Hardie, 2000; Yang et al., 2010).
In this work we i) extend the beta-binomial negative-binomial (BBNB)
model (Hofler and Scrogin, 2008) with a hurdle component to improve
modeling excess zeros in panel data (§2); ii) present the maximum likelihood
estimator (MLE) and also add prior information on missingness (§3); and
iii) use the methodology to estimate – from online media panels and internal
YouTube log files – how many people in Germany visit YouTube (§4).
The proposed methodology can be applied to a great variety of situations
where events have been counted – but some are known to be missing.2 How Many People Visit YouTube?
2 Hierarchical Event Imputation
Let Ni ∈ {0, 1, 2, . . .} count the true (but unobserved) number of visits by
panelist i. The population consists of people who do not visit YouTube at
all (with probability q0 ∈ [0, 1]), and those who visit at least once. If she
visits (overcoming the “hurdle” with probability 1 − q0), we assume that
Ni
is distributed according to a shifted Poisson distribution (starting at
n = 1) with rate λi
. For model heterogeneity among the population we use
a Gamma
r,
q1
1−q1
prior for λi
, with r > 0 and q1 ∈ (0, 1).
Overall, this yields a shifted negative binomial hurdle (NBH) distribution
P (N = n; q0, q1, r) = (
q0, if n = 0,
(1 − q0) ·
Γ(n+r−1)
Γ(r)Γ(n)
· (1 − q1)
r
q
n−1
1
, if n ≥ 1.
(1)
We choose a hurdle, rather than a mixture, model for the excess zeros (Hu
et al., 2011), since 1 − q0 can be directly interpreted as the true – but
unobserved – 1+ reach: if an advertiser shows an ad on YouTube they can
expect that a fraction of 1 − q0 of the population sees it at least once.
Let pi be the probability a visit of user i is recorded in the panel. Assuming
independence across visits the total number of recorded panel events,
Ki ∈ {0, 1, 2, . . .}, thus follows a binomial distribution, Ki ∼ Bin(Ni
, pi). To
account for heterogeneity across the population we assume pi ∼ Beta(µ, φ),
with mean µ and precision φ (Ferrari and Cribari-Neto, 2004). Here µ represents
the expected non-missing rate and φ the (inverse) variation across
the population. Integrating out pi gives a Beta-Binomial (BB) distribution,
Ki
| Ni ∼ BB(Ni
; µ, φ). (2)
Combining (1) and (2) yields a hierarchical beta-binomial negative-binomial
hurdle (BBNBH) imputation model with parameter vector θ = (µ, φ, q0, r, q1):
Ni ∼ NBH(N; q0, r, q1) and Ki
| Ni ∼ BB(K | Ni
; µ, φ). (3)
2.1 Joint Distribution
The pdf of (2) can be written as
g(k | n; µ, φ) =
n
k
Γ(k + φµ)Γ(n − k + (1 − µ)φ)
Γ(n + φ)
Γ(φ)
Γ(µφ)Γ(φ(1 − µ)) .
For k = 0 this reduces to
P (K = 0 | N, µ, φ) = Γ(n + (1 − µ)φ)
Γ(n + φ)
×
Γ(φ)
Γ(φ(1 − µ)) . (4)Goerg et al. 3
Due to the zero hurdle it is useful to treat N = 0 and N > 0 separately:
P (N, K) = P (K | N) · P (N) = BB(k | n; µ, φ) · NBH(n; q0, q1, r) (5)
For n = 0, (5) is non-zero only for k = 0, P (N = 0, K = 0) = q0, since
P (K > N) = 0. For n > 0,
P (N = n, K = k) =(1 − q0)
1
B(φµ, φ(1 − µ))
(1 − q1)
r
Γ(r)
×
Γ(k + φµ)
Γ(k + 1)
×
Γ(n − k + φ(1 − µ))
Γ(n − k + 1)
Γ(n + r − 1)
Γ(n + φ)
q
n−1
1 ×
Γ(n + 1)
Γ(n)
.
(6)
2.2 Conditional Predictive Distribution For Imputation
The panel records ki events for panelist i, but we want to know how many
events truly occurred. That is, we are interested in (dropping subscript i)
P (N = n | K = k) = P (K = k | N = n) P (N = n)
P (K = k)
, (7)
To obtain analytical expressions we consider k = 0 and k > 0 separately:
k = 0: Either none truly happened (n = 0) or a panelist visited at least
once (n > 0), but none were recorded.
n = 0:
P (N = 0 | K = 0) = q0
P (K = 0). (8)
n > 0:
P (N = n | K = 0) = 1
P (K = 0) ×
Γ(n + φ(1 − µ))
Γ(n + φ)
Γ(φ)
Γ(φ(1 − µ))
× (1 − q0)
Γ(n + r − 1)
Γ(n)
(1 − q1)
r
Γ(r)
q
n−1
1
,
where the second term comes from (4).
k > 0: The zero “hurdle” for N has been surpassed for sure.
n < k : By construction of Binomial subsampling
P (N = n | K = k) = 0 for all n < k. (9)
n ≥ k: Here
P (N = n | K = k) = n · q
n−1
1
Γ(n − k + (1 − µ)φ)
Γ(n − k + 1)Γ(n + φ)
Γ(n + r − 1)×
X∞
m=0
(m + k)
Γ(m + φ(1 − µ))
Γ(m + 1)
Γ(m + k + r − 1)
Γ(m + k + φ)
q
m+k−1
1
!−1
.4 How Many People Visit YouTube?
Estimate Std. Err. t value P r(> |t|)
µ 0.272
q0 0.641 0.016 38.858 0.000
q1 0.982 0.002 494.105 0.000
r 0.252 0.021 11.811 0.000
φ 2.320 0.594 3.907 0.000
TABLE 1: MLE for θ for panel data on YouTube visits in Germany.
3 Parameter Estimation
Let k = {k1, . . . , kP } be the number of observed events for all P panelist.
Each panelist also has socio-economic indicators such as gender, age, and
income. These attributes determine their demographic weight ˜wi
, which
equals the number of people in the entire population that panelist i represents.
Finally, let wi = ˜wi
·
P/PP
i=1 w˜i
be re-scaled weight of panelist i
such that PP
i=1 wi equals sample size P.
We estimate θ using maximum likelihood (MLE), θb = arg maxθ∈Θ `(θ; x),
where the log-likelihood
`(θ; x) = X
{k|xk>0}
xk · log P (K = k; θ), (10)
and x = {xk | k = 0, 1, . . . , max (k)}, where xk =
P
{i|ki=k} wi
is the total
weight of all panelists with k visits.
For deriving closed form expressions of P (K = k) = P∞
n=0 P (N = n, K = k)
it is simpler to consider k = 0 and k > 0 separately:
P (K = 0) = q0 + (1 − q0) ×
Γ(φ)
Γ(φ(1 − µ))
(1 − q1)
r
Γ(r)
×
X∞
n=0
Γ(n + 1 + φ(1 − µ))
Γ(n + 1)
Γ(n + r)
Γ(n + 1 + φ)
q
n
1
,
(11)
and for k > 0,
P (K = k) =(1 − q0)(1 − q1)
r Γ(φ)
Γ(µφ)Γ(φ(1 − µ))
1
Γ(r)
×
Γ(k + µφ)
Γ(k + 1)
×
X∞
m=0
(m + k)
Γ(m + φ(1 − µ))
Γ(m + 1)
Γ(m + k + r − 1)
Γ(m + k + φ)
q
m+k−1
1
.
(12)Goerg et al. 5
0 4 8 12 17 22
cdf
0.65 0.80
P(N <= n; r = 0.25, q1 = 0.98, q0 = 0.64)
true counts (N)
q0 = 64
%
0.0 0.2 0.4 0.6 0.8 1.0
0 1 2
3
4
5
pdf
Beta(p; µ = 0.27, φ = 2.3)
non−missingness rate
α = 0.63, β = 1.7
0 5 10 15 20 25
0.80
cdf
0.90
●
●
●
●
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
P(K <= k; θ)
observed counts (K)
●
empirical
model
Log−likelihood: −6466.69
0 2 4 6 8 10
K = 0
K = 2
pmf
0.0 0.4 0.8
P(N = n | K = k; θ)
true counts (N)
E(N|K=0) = 1.02
E(N|K=2) = 13.12
79.5%
FIGURE 1: Model estimates for: (top left) true counts Ni
; (top right) nonmissing
rate pi
; (bottom left) empirical count frequency and model fit;
(bottom right) conditional predictive distributions and expectations.
3.1 Fix expected non-missing rate µ
Usually, researchers must estimate all 5 parameters from panel data. For
our application, though, we can estimate (and fix) the non-missing rate µ
a-priori as we have access to internal YouTube log files.
Let ¯kW˜ =
PP
i=1 w˜iki be the observed panel visits projected to the entire
population. Analogously, let N¯W˜ =
PP
i=1 w˜iNi be the panel projections of
the number of true YouTube visits. While any single Ni
is unobservable,
we can estimate N¯W˜ by simply counting all YouTube homepage views in
Germany from our YouTube log files, yielding Nb¯W˜ . We herewith obtain a
plug-in estimate of the non-missing rate, µbLogs = ¯kW˜ /Nb¯W˜ . The remaining
4 parameters, θ(−µ) = (φ, q0, r, q1), can be obtained by MLE, θb
(−µ) =
arg maxθ(−µ)
`((µbLogs, θ(−µ)); x). The overall estimate is θb = (µbLogs, θb
(−µ)).
4 Estimating YouTube Audience in Germany
Here we use data from a German online panel (GfK Consumer Panels,
2013), which monitors web usage of P = 6, 545 individuals in October, 2013
(31 days). In particular, we are interested in the probability that an adult
in Germany visited the YouTube homepage www.youtube.de. Empirically,Pb (K = 0) = 0.81, yielding 19% observed 1+ reach. However, we know by
comparison to YouTube log files that the panel only recorded 27.2% of all
impressions. We fix the expected non-missing rate at µb = 0.272 and obtain
the remaining parameters via MLE (Table 1): Figure 1 shows the model fit
for the true, observed, and predictive distribution. In particular, the true
1+ reach is 36% (qb0 = 0.64), not 19% as the na¨ıve estimate suggests.
5 Discussion
We introduce a probabilistic framework to impute missing events in count
data, including a hurdle component for more flexibility to model lots of zeros.
Researchers can use our models to obtain accurate probabilistic predictions
of the number of true, unobserved events. We apply our methodology
to accurately estimate how many people in Germany visit YouTube.
Acknowledgments: We want to thank Christoph Best, Penny Chu, Tony
Fagan, Yijia Feng, Oli Gaymond, Simon Morris, Raimundo Mirisola, Andras
Orban, Simon Rowe, Sheethal Shobowale, Yunting Sun, Wiesner Vos,
Xiaojing Wang, and Fan Zhang for constructive discussions and feedback.
References
Fader, P. and Hardie, B. (2000). A note on modelling underreported Poisson
counts. Journal of Applied Statistics, 27(8):953–964.
Ferrari, S. and Cribari-Neto, F. (2004). Beta Regression for Modelling
Rates and Proportions. Journal of Applied Statistics, 31(7):799–815.
GfK Consumer Panels (2013). Media Efficiency Panel.
Hofler, R. A. and Scrogin, D. (2008). A count data frontier model. Technical
report, University of Central Florida.
Hu, M., Pavlicova, M., and Nunes, E. (2011). Zero-inflated and hurdle models
of count data with extra zeros: examples from an HIV-risk reduction
intervention trial. Am J Drug Alcohol Abuse, 37(5):367–75.
Rose, C., Martin, S., Wannemuehler, K., and Plikaytis, B. (2006). On the
use of zero-inflated and hurdle models for modeling vaccine adverse event
count data. J Biopharm Stat, 16(4):463–81.
Schmittlein, D. C., Bemmaor, A. C., and Morrison, D. G. (1985). Why
Does the NBD Model Work? Robustness in Representing Product Purchases,
Brand Purchases and Imperfectly Recorded Purchases. Marketing
Science, 4(3):255–266.
Yang, S., Zhao, Y., and Dhar, R. (2010). Modeling the underreporting bias
in panel survey data. Marketing Science, 29(3):525–539.
38 COMMUNICATIONS OF THE ACM | SEPTEMBER 2014 | VOL. 57 | NO. 9
practice
DOI:10.1145/2643134
Article development led by
queue.acm.org
Preventing script injection vulnerabilities
through software design.
BY CHRISTOPH KERN
SCRIPT INJECTION VULNERABILITIES are a bane of
Web application development: deceptively simple in
cause and remedy, they are nevertheless surprisingly
difficult to prevent in large-scale Web development.
Cross-site scripting (XSS)2,7,8 arises when insufficient
data validation, sanitization, or escaping within a Web
application allow an attacker to cause browser-side
execution of malicious JavaScript in
the application’s context. This injected
code can then do whatever the attacker
wants, using the privileges of the victim.
Exploitation of XSS bugs results
in complete (though not necessarily
persistent) compromise of the victim’s
session with the vulnerable application.
This article provides an overview
of how XSS vulnerabilities arise and
why it is so difficult to avoid them in
real-world Web application software
development. Software design patterns
developed at Google to address
the problem are then described.
A key goal of these design patterns
Securing
the
Tangled
WebSEPTEMBER 2014 | VOL. 57 | NO. 9 | COMMUNICATIONS OF THE ACM 39
IMAGE BY PHOTOBANK GALLERY
is to confine the potential for XSS
bugs to a small fraction of an application’s
code base, significantly improving
one’s ability to reason about the
absence of this class of security bugs.
In several software projects within
Google, this approach has resulted in a
substantial reduction in the incidence
of XSS vulnerabilities.
Most commonly, XSS vulnerabilities
result from insufficiently validating,
sanitizing, or escaping strings that
are derived from an untrusted source
and passed along to a sink that interprets
them in a way that may result in
script execution.
Common sources of untrustworthy
data include HTTP request parameters,
as well as user-controlled data located
in persistent data stores. Strings
are often concatenated with or interpolated
into larger strings before assignment
to a sink. The most frequently
encountered sinks relevant to XSS
vulnerabilities are those that interpret
the assigned value as HTML markup,
which includes server-side HTTP responses
of MIME-type text/html, and
the Element.prototype.innerHTML
Document Object Model (DOM)8
property
in browser-side JavaScript code.
Figure 1a shows a slice of vulnerable
code from a hypothetical photosharing
application. Like many modern
Web applications, much of its
user-interface logic is implemented in
browser-side JavaScript code, but the
observations made in this article transfer
readily to applications whose UI is
implemented via traditional serverside
HTML rendering.
In code snippet (1) in the figure,
the application generates HTML
markup for a notification to be shown
to a user when another user invites
the former to view a photo album.
The generated markup is assigned to
the innerHTML property of a DOM 40 COMMUNICATIONS OF THE ACM | SEPTEMBER 2014 | VOL. 57 | NO. 9
practice
main page. If the login resulted from
a session time-out, however, the app
navigates back to the URL the user
had visited before the time-out. Using
a common technique for short-term
state storage in Web applications,
this URL is encoded in a parameter of
the current URL.
The page navigation is implemented
via assignment to the window.location.href
DOM property, which
browsers interpret as instruction to
navigate the current window to the
provided URL. Unfortunately, navigating
a browser to a URL of the form
javascript:attackScript causes
execution of the URL’s body as Java
Script. In this scenario, the target
URL is extracted from a parameter of
the current URL, which is generally
under attacker control (a malicious
page visited by a victim can instruct
the browser to navigate to an attacker-chosen
URL).
Thus, this code is also vulnerable
to XSS. To fix the bug, it is necessary to
validate that the URL will not result in
script execution when dereferenced, by
ensuring that its scheme is benign—
for example, https.
Why Is XSS So Difficult to Avoid?
Avoiding the introduction of XSS into
nontrivial applications is a difficult
problem in practice: XSS remains
among the top vulnerabilities in Web
applications, according to the Open
Web Application Security Project
(OWASP);4
within Google it is the most
common class of Web application vulnerabilities
among those reported under
Google’s Vulnerability Reward Program
(https://goo.gl/82zcPK).
Traditionally, advice (including my
own) on how to prevent XSS has largely
focused on:
˲ Training developers how to treat
(by sanitization, validation, and/or escaping)
untrustworthy values interpolated
into HTML markup.2,5
˲ Security-reviewing and/or testing
code for adherence to such guidance.
In our experience at Google, this approach
certainly helps reduce the incidence
of XSS, but for even moderately
complex Web applications, it does not
prevent introduction of XSS to a reasonably
high degree of confidence. We
see a combination of factors leading to
this situation.
element (a node in the hierarchical
object representation of UI elements
in a browser window), resulting in its
evaluation and rendering.
The notification contains the album’s
title, chosen by the second user. A malicious
user can create an album titled:
Since no escaping or validation is
applied, this attacker-chosen HTML is
interpolated as-is into the markup generated
in code snippet (1). This markup
is assigned to the innerHTML sink,
and hence evaluated in the context of
the victim’s session, executing the attacker-chosen
JavaScript code.
To fix this bug, the album’s title
must be HTML-escaped before use in
markup, ensuring that it is interpreted
as plain text, not markup. HTMLescaping
replaces HTML metacharacters
such as <, >, ", ', and & with corresponding
character entity references
or numeric character references: <,
>, ", ', and &. The
result will then be parsed as a substring
in a text node or attribute value
and will not introduce element or attribute
boundaries.
As noted, most data flows with a
potential for XSS are into sinks that
interpret data as HTML markup. But
other types of sinks can result in XSS
bugs as well: Figure 1b shows another
slice of the previously mentioned
photo-sharing application, responsible
for navigating the user interface
after a login operation. After a fresh
login, the app navigates to a preconfigured
URL for the application’s
The following code snippet intends to populate a DOM element with markup for a
hyperlink (an HTML anchor element):
var escapedCat = goog.string.htmlEscape(category);
var jsEscapedCat = goog.string.escapeString(escapedCat);
catElem.innerHTML = '' + escapedCat + '';
The anchor element’s click-event handler, which is invoked by the browser when
a user clicks on this UI element, is set up to call a JavaScript function with the value of
category as an argument. Before interpolation into the HTML markup, the value of
category is HTML-escaped using an escaping function from the JavaScript Closure
Library. Furthermore, it is JavaScript-string-literal-escaped (replacing ' with \' and
so forth) before interpolation into the string literal within the onclick handler’s
JavaScript expression. As intended, for a value of Flowers & Plants for variable
category, the resulting HTML markup is:
Flowers & Plants
So where’s the bug? Consider a value for category of:
');attackScript();//
Passing this value through htmlEscape results in:
');attackScript();//
because htmlEscape escapes the single quote into an HTML character reference.
After this, JavaScript-string-literal escaping is a no-op, since the single quote at the
beginning of the page is already HTML-escaped. As such, the resulting markup becomes:
');attackScript();//
When evaluating this markup, a browser will first HTML-unescape the value of the
onclick attribute before evaluation as a JavaScript expression. Hence, the JavaScript
expression that is evaluated results in execution of the attacker’s script:
createCategoryList('');attackScript();//')
Thus, the underlying bug is quite subtle: the programmer invoked the appropriate
escaping functions, but in the wrong order.
A Subtle XSS BugSEPTEMBER 2014 | VOL. 57 | NO. 9 | COMMUNICATIONS OF THE ACM 41
practice
Subtle security considerations.
As seen, the requirements for secure
handling of an untrustworthy value
depend on the context in which the
value is used. The most commonly
encountered context is string interpolation
within the content of HTML
markup elements; here, simple
HTML-escaping suffices to prevent
XSS bugs. Several special contexts,
however, apply to various DOM elements
and within certain kinds of
markup, where embedded strings are
interpreted as URLs, Cascading Style
Sheets (CSS) expressions, or JavaScript
code. To avoid XSS bugs, each of
these contexts requires specific validation
or escaping, or a combination
of the two.2,5 The accompanying sidebar,
“A Subtle XSS Bug,” shows this
can be quite tricky to get right.
Complex, difficult-to-reason-about
data flows. Recall that XSS arises from
flows of untrustworthy, unvalidated/escaped
data into injection-prone sinks.
To assert the absence of XSS bugs in
an application, a security reviewer
must first find all such data sinks, and
then inspect the surrounding code for
context-appropriate validation and escaping
of data transferred to the sink.
When encountering an assignment
that lacks validation and escaping, the
reviewer must backward-trace this data
flow until one of the following situations
can be determined:
˲ The value is entirely under application
control and hence cannot result in
attacker-controlled injection.
˲ The value is validated, escaped,
or otherwise safely constructed somewhere
along the way.
˲ The value is in fact not correctly
validated and escaped, and an XSS vulnerability
is likely present.
Let’s inspect the data flow into
the innerHTML sink in code snippet
(1) in Figure 1a. For illustration purposes,
code snippets and data flows
that require investigation are shown
in red. Since no escaping is applied
to sharedAlbum.title, we trace its
origin to the albums entity (4) in persistent
storage, via Web front-end code
(2). This is, however, not the data’s ultimate
origin—the album name was previously
entered by a different user (that
is, originated in a different time context).
Since no escaping was applied to
this value anywhere along its flow from
an ultimately untrusted source, an XSS
vulnerability arises.
Similar considerations apply to the
data flows in Figure 1b: no validation
occurs immediately prior to the assignment
to window.location.href
in (5), so back-tracing is necessary. In
code snippet (6), the code exploration
branches: in the true branch, the value
originates in a configuration entity in
the data store (3) via the Web front end
(8); this value can be assumed application-controlled
and trustworthy and is
safe to use without further validation.
It is noteworthy that the persistent
storage contains both trustworthy and
untrustworthy data in different entities
of the same schema—no blanket
assumptions can be made about the
provenance of stored data.
In the else-branch, the URL originates
from a parameter of the current
URL, obtained from window.location.href,
which is an attacker-controlled
source (7). Since there is no validation,
this code path results in an XSS
vulnerability.
Many opportunities for mistakes.
Figures 1a and 1b show only two small
slices of a hypothetical Web application.
In reality, a large, nontrivial Web
application will have hundreds if not
thousands of branching and merging
data flows into injection-prone sinks.
Each such flow can potentially result in
an XSS bug if a developer makes a mistake
related to validation or escaping.
Exploring all these data flows and
asserting absence of XSS is a monumental
task for a security reviewer, especially
considering an ever-changing
code base of a project under active
development. Automated tools that
employ heuristics to statically analyze
data flows in a code base can help. In
our experience at Google, however,
they do not substantially increase confidence
in review-based assessments,
since they are necessarily incomplete
in their reasoning and subject to both
false positives and false negatives. Furthermore,
they have similar difficulties
as human reviewers with reasoning
about whole-system data flows across
multiple system components, using
a variety of programming languages,
RPC (remote procedure call) mechanisms,
and so forth, and involving
flows traversing multiple time contexts
across data stores.
The primary
goal of this
approach is to
limit code that
could potentially
give rise to XSS
vulnerabilities
to a very small
fraction of
an application’s
code base.42 COMMUNICATIONS OF THE ACM | SEPTEMBER 2014 | VOL. 57 | NO. 9
practice
user-profile field).
Unfortunately, there is an XSS bug:
the markup in profile.aboutHtml
ultimately originates in a rich-text editor
implemented in browser-side code,
but there is no server-side enforcement
preventing an attacker from injecting
malicious markup using a tampered-with
client. This bug could arise
in practice from a misunderstanding
between front-end and back-end developers
regarding responsibilities for
data validation and sanitization.
Reliably Preventing the
Introduction of XSS Bugs
In our experience in Google’s security
team, code inspection and testing do
not ensure, to a reasonably high degree
of confidence, the absence of XSS bugs
in large Web applications. Of course,
both inspection and testing provide
tremendous value and will typically
find some bugs in an application (perhaps
even most of the bugs), but it is
difficult to be sure whether or not they
discovered all the bugs (or even almost
all of them).
The primary goal of this approach is
to limit code that could potentially give
rise to XSS vulnerabilities to a very small
fraction of an application’s code base.
A key goal of this approach is to
drastically reduce the fraction of code
that could potentially give rise to
XSS bugs. In particular, with this approach,
an application is structured
such that most of its code cannot be
responsible for XSS bugs. The potential
for vulnerabilities is therefore
confined to infrastructure code such
as Web application frameworks and
HTML templating engines, as well
as small, self-contained applicationspecific
utility modules.
A second, equally important goal is
to provide a developer experience that
does not add an unacceptable degree
of friction as compared with existing
developer workflows.
Key components of this approach
are:
˲ Inherently safe APIs. Injection-prone
Web-platform and HTML-rendering
APIs are encapsulated in wrapper APIs
designed to be inherently safe against
XSS in the sense that no use of such
APIs can result in XSS vulnerabilities.
˲ Security type contracts. Special
types are defined with contracts stipuSimilar
limitations apply to dynamic
testing approaches: it is difficult to
ascertain whether test suites provide
adequate coverage for whole-system
data flows.
Templates to the rescue? In practice,
HTML markup, and interpolation
points therein, are often specified using
HTML templates. Template systems
expose domain-specific languages for
rendering HTML markup. An HTML
markup template induces a function
from template variables into strings of
HTML markup.
Figure 1c illustrates the use of an
HTML markup template (9): this example
renders a user profile in the
photo-sharing application, including
the user’s name, a hyperlink to a personal
blog site, as well as free-form
text allowing the user to express any
special interests.
Some template engines support
automatic escaping, where escaping
operations are automatically inserted
around each interpolation point into
the template. Most template engines’
auto-escape facilities are noncontextual
and indiscriminately apply HTML
escaping operations, but do not account
for special HTML contexts such
as URLs, CSS, and JavaScript.
Contextually auto-escaping template
engines6
infer the necessary
validation and escaping operations required
for the context of each template
substitution, and therefore account for
such special contexts.
Use of contextually auto-escaping
template systems dramatically reduces
the potential for XSS vulnerabilities: in
(9), the substitution of untrustworthy
values profile.name and profile.
blogUrl into the resulting markup
cannot result in XSS—the template system
automatically infers the required
HTML-escaping and URL-validation.
XSS bugs can still arise, however,
in code that does not make use of templates,
as in Figure 1a (1), or that involves
non-HTML sinks, as in Figure 1b (5).
Furthermore, developers occasionally
need to exempt certain substitutions
from automatic escaping: in Figure 1c
(9), escaping of profile.aboutHtml
is explicitly suppressed because that
field is assumed to contain a user-supplied
message with simple, safe HTML
markup (to support use of fonts, colors,
and hyperlinks in the “about myself”
lating that their values are safe to use
in specific contexts without further escaping
and validation.
˲ Coding guidelines. Coding guidelines
restrict direct use of injectionprone
APIs, and ensure security review
of certain security-sensitive APIs. Adherence
to these guidelines can be enforced
through simple static checks.
Inherently safe APIs. Our goal is
to provide inherently safe wrapper
APIs for injection-prone browser-side
Web platform API sinks, as well as for
server- and client-side HTML markup
rendering.
For some APIs, this is straightforward.
For example, the vulnerable assignment
in Figure 1b (5) can be replaced
with the use of an inherently
safe wrapper API, provided by the JavaScript
Closure Library, as shown in
Figure 2b (5’). The wrapper API validates
at runtime that the supplied URL
represents either a scheme-less URL or
one with a known benign scheme.
Using the safe wrapper API ensures
this code will not result in an XSS
vulnerability, regardless of the provenance
of the assigned URL. Crucially,
none of the code in (5’) nor its fan-in
in (6-8) needs to be inspected for XSS
bugs. This benefit comes at the very
small cost of a runtime validation that
is technically unnecessary if (and only
if) the first branch is taken—the URL
obtained from the configuration store
is validated even though it is actually a
trustworthy value.
In some special scenarios, the runtime
validation imposed by an inherently
safe API may be too strict. Such
cases are accommodated via variants
of inherently safe APIs that accept
types with a security contract appropriate
for the desired use context. Based
on their contract, such values are exempt
from runtime validation. This
approach is discussed in more detail in
the next section.
Strictly contextually auto-escaping
template engines. Designing an inherently
safe API for HTML rendering is
more challenging. The goal is to devise
APIs that guarantee that at each substitution
point of data into a particular
context within trusted HTML markup,
data is appropriately validated, sanitized,
and/or escaped, unless it can be
demonstrated that a specific data item
is safe to use in that context based on SEPTEMBER 2014 | VOL. 57 | NO. 9 | COMMUNICATIONS OF THE ACM 43
practice
Figure 1. XSS vulnerabilities in a hypothetical Web application.
Browser Web-App Frontend Application Backends
(4)
(3)
(1)
Application data store
(2)
Browser Web-App Frontend Application Backends
(4)
(3)
(5)
(6)
(7)
Application data store
(8)
Browser Web-App Frontend Application Backends
(12)
(13)
(9)
(10)
Profile Store
(11)
(a) Vulnerable code of a hypothetical photo-sharing application.
(b) Another slice of the photo-sharing application.
(c) Using an HTML markup template. 44 COMMUNICATIONS OF THE ACM | SEPTEMBER 2014 | VOL. 57 | NO. 9
practice
sanitizer to remove any markup that
may result in script execution renders
it safe to use in HTML context and
thus produces a value that satisfies the
SafeHtml type contract.
To actually create values of these
types, unchecked conversion factory
methods are provided that consume
an arbitrary string and return an instance
of a given wrapper type (for example,
SafeHtml or SafeUrl) without
applying any runtime sanitization
or escaping.
Every use of such unchecked conversions
must be carefully security reviewed
to ensure that in all possible
program states, strings passed to the
conversion satisfy the resulting type’s
contract, based on context-specific
processing or construction. As such,
unchecked conversions should be used
as rarely as possible, and only in scenarios
where their use is readily reasoned
about for security-review purposes.
For example, in Figure 2c, the unchecked
conversion is encapsulated
in a library (12’’) along with the HTML
sanitizer implementation on whose
correctness its use depends, permitting
security review and testing in isolation.
Coding guidelines. For this approach
to be effective, it must ensure
developers never write application
code that directly calls potentially injection-prone
sinks, and that they instead
use the corresponding safe wrapper
API. Furthermore, it must ensure
uses of unchecked conversions are designed
with reviewability in mind, and
are in fact security reviewed. Both constraints
represent coding guidelines
with which all of an application’s code
base must comply.
In our experience, automated enforcement
of coding guidelines is
necessary even in moderate-size projects—otherwise,
violations are bound
to creep in over time.
At Google we use the open source
error-prone static checker1
(https://
goo.gl/SQXCvw), which is integrated
into Google’s Java tool chain, and a feature
of Google’s open source Closure
Compiler (https://goo.gl/UyMVzp) to
whitelist uses of specific methods
and properties in JavaScript. Errors
arising from use of a “banned” API
include references to documentation
for the corresponding safe API, advising
developers on how to address
its provenance or prior validation, sanitization,
or escaping.
These inherently safe APIs are created
by strengthening the concept of
contextually auto-escaping template
engines6
into SCAETEs (strictly contextually
auto-escaping template engines).
Essentially, a SCAETE places two additional
constraints on template code:
˲ Directives that disable or modify the
automatically inferred contextual escaping
and validation are not permitted.
˲ A template may use only sub-templates
that recursively adhere to the
same constraint.
Security type contracts. In the form
just described, SCAETEs do not account
for scenarios where template
parameters are intended to be used
without validation or escaping, such
as aboutHtml in Figure 1c—the
SCAETE unconditionally validates
and escapes all template parameters,
and disallows directives to disable the
auto-escaping mechanism.
Such use cases are accommodated
through types whose contracts stipulate
their values are safe to use in corresponding
HTML contexts, such as
“inner HTML,” hyperlink URLs, executable
resource URLs, and so forth.
Type contracts are informal: a value
satisfies a given type contract if it is
known that it has been validated, sanitized,
escaped, or constructed in a way
that guarantees its use in the type’s target
context will not result in attackercontrolled
script execution. Whether
or not this is indeed the case is established
by expert reasoning about code
that creates values of such types, based
on expert knowledge of the relevant
behaviors of the Web platform.8
As will
be seen, such security-sensitive code
is encapsulated in a small number of
special-purpose libraries; application
code uses those libraries but is itself
not relied upon to correctly create instances
of such types and hence does
not need to be security-reviewed.
The following are examples of types
and type contracts in use:
˲ SafeHtml. A value of type
SafeHtml, converted to string, will not
result in attacker-controlled script execution
when used as HTML markup.
˲ SafeUrl. Values of this type will
not result in attacker-controlled script
execution when dereferenced as hyperlink
URLs.
˲ TrustedResourceUrl. Values
of this type are safe to use as the
URL of an executable or “control” resource,
such as the src attribute of a
Voir également :
![[TXT]](http://www.audentia-gestion.fr/icons/text.gif)
01AINrues.htm 07-Oct-2011 14:09 5.5M
75PARISRUEMONTGALLET..> 19-Oct-2011 11:58 32K
75PARISavenuedescham..> 19-Oct-2011 11:50 521K
75PARISruedeRennesen..> 19-Oct-2011 12:09 203K
75PARISruegeneralDel..> 19-Oct-2011 12:04 17K
75PARISrues.htm 11-Jul-2011 20:49 3.6M
78YVELINESrues.htm 11-Jul-2011 20:55 2.0M
92HAUTSDESEINErues.htm 12-Jul-2011 09:21 4.1M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:19 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:19 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:19 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:18 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:18 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:18 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:18 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:17 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 09:17 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:03 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:09 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:09 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:21 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:24 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:23 1.7M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:23 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:23 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:23 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:22 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:22 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:22 1.6M
Rues-06-Alpes-Mariti..> 04-Jul-2013 08:22 1.6M
Rues-1.htm 04-Jun-2013 12:57 2.9M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:31 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:31 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:31 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:30 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:30 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:30 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:30 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:29 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:29 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:29 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:29 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:28 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:28 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:28 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 07:28 1.5M
Rues-13-Bouches-du-R..> 27-Jun-2013 10:12 1.9M
Rues-33-Gironde-1.htm 27-Jun-2013 16:39 1.9M
Rues-33-Gironde-2.htm 27-Jun-2013 16:39 1.9M
Rues-33-Gironde-3.htm 27-Jun-2013 16:38 1.9M
Rues-33-Gironde-4.htm 27-Jun-2013 16:38 1.9M
Rues-33-Gironde-5.htm 27-Jun-2013 16:46 1.9M
Rues-33-Gironde-6.htm 27-Jun-2013 16:46 1.9M
Rues-33-Gironde-7.htm 27-Jun-2013 16:46 1.9M
Rues-33-Gironde-8.htm 27-Jun-2013 16:46 1.9M
Rues-33-Gironde-9.htm 27-Jun-2013 16:45 1.9M
Rues-33-Gironde-10.htm 27-Jun-2013 16:45 1.9M
Rues-33-Gironde-11.htm 27-Jun-2013 16:53 1.9M
Rues-33-Gironde-12.htm 27-Jun-2013 16:53 1.9M
Rues-33-Gironde-13.htm 27-Jun-2013 16:53 1.9M
Rues-33-Gironde-14.htm 27-Jun-2013 16:52 1.9M
Rues-33-Gironde-15.htm 28-Jun-2013 08:05 1.9M
Rues-33-Gironde-16.htm 28-Jun-2013 08:03 1.9M
Rues-33-Gironde-17.htm 28-Jun-2013 08:03 1.9M
Rues-33-Gironde-18.htm 28-Jun-2013 07:37 1.9M
Rues-33-Gironde-19.htm 28-Jun-2013 07:37 1.9M
Rues-33-Gironde-20.htm 28-Jun-2013 07:36 1.9M
Rues-33-Gironde-21.htm 28-Jun-2013 07:36 1.9M
Rues-33-Gironde-22.htm 28-Jun-2013 07:35 1.9M
Rues-33-Gironde-23.htm 28-Jun-2013 07:35 1.9M
Rues-33-Gironde-24.htm 28-Jun-2013 07:35 1.9M
Rues-33-Gironde-25.htm 28-Jun-2013 07:35 1.9M
Rues-33-Gironde-26.htm 28-Jun-2013 07:34 1.9M
Rues-33-Gironde-27.htm 28-Jun-2013 08:13 1.9M
Rues-33-Gironde-28.htm 28-Jun-2013 08:12 1.9M
Rues-33-Gironde-29.htm 28-Jun-2013 08:12 1.9M
Rues-33-Gironde-30.htm 28-Jun-2013 08:12 1.9M
Rues-33-Gironde-31.htm 28-Jun-2013 08:12 1.9M
Rues-33-Gironde-32.htm 28-Jun-2013 08:23 1.9M
Rues-33-Gironde-33.htm 28-Jun-2013 08:23 1.9M
Rues-33-Gironde-34.htm 28-Jun-2013 08:25 2.3M
Rues-33-Gironde-35.htm 28-Jun-2013 08:25 2.3M
Rues-33-Gironde-36.htm 28-Jun-2013 08:24 2.2M
Rues-33-Gironde-37.htm 28-Jun-2013 08:24 2.2M
Rues-33-Gironde-38.htm 28-Jun-2013 08:26 2.3M
Rues-33-Gironde-43.htm 28-Jun-2013 09:39 2.2M
Rues-33-Gironde-44.htm 28-Jun-2013 09:39 2.3M
Rues-33-Gironde-45.htm 28-Jun-2013 09:38 2.3M
Rues-33-Gironde-46.htm 28-Jun-2013 09:38 2.2M
Rues-33-Gironde-47.htm 28-Jun-2013 09:38 2.3M
Rues-33-Gironde-48.htm 28-Jun-2013 09:38 2.3M
Rues-33-Gironde-49.htm 28-Jun-2013 09:37 2.3M
Rues-33-Gironde-50.htm 28-Jun-2013 09:37 2.3M
Rues-33-Gironde-51.htm 28-Jun-2013 09:36 2.3M
Rues-33-Gironde-52.htm 28-Jun-2013 09:42 2.3M
Rues-59-Nord-59000-L..> 03-Jul-2013 07:15 2.2M
Rues-59-Nord-59000-T..> 03-Jul-2013 07:17 2.1M
Rues-59-Nord-59200-T..> 03-Jul-2013 07:17 2.1M
Rues-59-Nord-59300-V..> 03-Jul-2013 07:17 2.1M
Rues-59-Nord-59400-C..> 03-Jul-2013 07:16 2.1M
Rues-59-Nord-59500-D..> 03-Jul-2013 07:16 2.1M
Rues-59-Nord-59600-M..> 03-Jul-2013 07:16 2.1M
Rues-59-Nord-59700-M..> 03-Jul-2013 07:15 2.1M
Rues-59-Nord-59800-L..> 03-Jul-2013 07:15 2.1M
Rues-59-Nord-A.htm 02-Jul-2013 09:41 2.2M
Rues-59-Nord-Allee.htm 29-Jun-2013 22:48 1.9M
Rues-59-Nord-Avenue.htm 29-Jun-2013 22:48 1.9M
Rues-59-Nord-B.htm 02-Jul-2013 09:41 2.1M
Rues-59-Nord-Bouleva..> 29-Jun-2013 22:47 1.9M
Rues-59-Nord-C.htm 02-Jul-2013 11:07 2.2M
Rues-59-Nord-Chausse..> 29-Jun-2013 22:47 1.9M
Rues-59-Nord-Chemin.htm 29-Jun-2013 22:47 1.9M
Rues-59-Nord-Chiffre..> 02-Jul-2013 09:41 2.1M
Rues-59-Nord-Cite.htm 29-Jun-2013 22:46 1.9M
Rues-59-Nord-Clos.htm 29-Jun-2013 22:46 1.9M
Rues-59-Nord-Cour.htm 29-Jun-2013 22:46 1.9M
Rues-59-Nord-D.htm 02-Jul-2013 11:16 2.3M
Rues-59-Nord-E.htm 02-Jul-2013 14:46 2.1M
Rues-59-Nord-F.htm 02-Jul-2013 14:46 2.1M
Rues-59-Nord-Hameau.htm 29-Jun-2013 22:45 1.9M
Rues-59-Nord-Impasse..> 30-Jun-2013 07:16 2.1M
Rues-59-Nord-Lieu.htm 01-Jul-2013 11:38 2.1M
Rues-59-Nord-Place.htm 01-Jul-2013 11:38 2.2M
Rues-59-Nord-Quai.htm 01-Jul-2013 11:37 2.1M
Rues-59-Nord-Residen..> 01-Jul-2013 11:37 2.1M
Rues-59-Nord-Route.htm 01-Jul-2013 11:38 2.1M
Rues-69-Rhone-1.htm 26-Jun-2013 18:48 1.5M
Rues-69-Rhone-2.htm 26-Jun-2013 18:48 1.5M
Rues-69-Rhone-3.htm 26-Jun-2013 18:48 1.5M
Rues-69-Rhone-4.htm 26-Jun-2013 18:47 1.5M
Rues-69-Rhone-5.htm 26-Jun-2013 18:47 1.5M
Rues-69-Rhone-6.htm 26-Jun-2013 18:47 1.5M
Rues-69-Rhone-7.htm 26-Jun-2013 18:47 1.5M
Rues-69-Rhone-8.htm 26-Jun-2013 18:46 1.5M
Rues-69-Rhone-9.htm 26-Jun-2013 18:46 1.5M
Rues-69-Rhone-10.htm 26-Jun-2013 18:46 1.5M
Rues-69-Rhone-11.htm 26-Jun-2013 18:46 1.5M
Rues-69-Rhone-12.htm 26-Jun-2013 18:45 1.5M
Rues-69-Rhone-13.htm 26-Jun-2013 18:45 1.5M
Rues-69-Rhone-14.htm 26-Jun-2013 18:45 1.5M
Rues-69-Rhone-15.htm 26-Jun-2013 18:45 1.5M
Rues-69-Rhone-16.htm 26-Jun-2013 18:44 1.5M
Rues-69-Rhone-17.htm 26-Jun-2013 18:44 1.5M
Rues-69-Rhone-18.htm 26-Jun-2013 18:44 1.5M
Rues-69-Rhone-19.htm 26-Jun-2013 18:44 1.5M
Rues-69-Rhone-20.htm 26-Jun-2013 18:43 1.5M
Rues-69-Rhone-21.htm 26-Jun-2013 18:49 1.5M
Rues-75-Paris-1.htm 26-Jun-2013 17:33 1.4M
Rues-75-Paris-2.htm 26-Jun-2013 17:33 1.5M
Rues-75-Paris-3.htm 26-Jun-2013 17:33 1.4M
Rues-75-Paris-4.htm 26-Jun-2013 17:32 1.4M
Rues-75-Paris-5.htm 26-Jun-2013 17:32 1.5M
Rues-75-Paris-6.htm 26-Jun-2013 17:32 1.5M
Rues-75-Paris-7.htm 26-Jun-2013 17:32 1.4M
Rues-75-Paris-8.htm 26-Jun-2013 17:31 1.4M
Rues-75-Paris-9.htm 26-Jun-2013 17:31 1.4M
Rues-75-Paris-10.htm 26-Jun-2013 17:31 1.5M
Rues-75-Paris-11.htm 26-Jun-2013 17:31 1.5M
Rues-75-Paris-12.htm 26-Jun-2013 17:30 1.5M
Rues-75-Paris-13.htm 26-Jun-2013 17:30 1.4M
Rues-75-Paris-Allee.htm 29-Jun-2013 21:59 2.2M
Rues-75-Paris-Avenue..> 29-Jun-2013 21:58 2.3M
Rues-75-Paris-Boulev..> 29-Jun-2013 21:58 2.3M
Rues-75-Paris-Chemin..> 29-Jun-2013 22:16 1.9M
Rues-75-Paris-Cite.htm 29-Jun-2013 22:15 1.9M
Rues-75-Paris-Cour.htm 29-Jun-2013 22:15 1.9M
Rues-77-Seine-et-Mar..> 04-Jul-2013 11:54 1.9M
Rues-77-Seine-et-Mar..> 04-Jul-2013 11:53 1.9M
Rues-77-Seine-et-Mar..> 04-Jul-2013 11:53 1.9M
Rues-77-Seine-et-Mar..> 04-Jul-2013 11:53 1.9M
Rues-77-Seine-et-Mar..> 04-Jul-2013 11:53 1.9M
Rues-77-Seine-et-Mar..> 04-Jul-2013 11:52 1.9M
Rues-77-Seine-et-Mar..> 04-Jul-2013 11:52 1.9M
Rues-78-Yvelines-1.htm 26-Jun-2013 09:14 1.7M
Rues-78-Yvelines-2.htm 26-Jun-2013 09:14 1.7M
Rues-78-Yvelines-3.htm 26-Jun-2013 09:14 1.7M
Rues-78-Yvelines-4.htm 26-Jun-2013 09:13 1.7M
Rues-78-Yvelines-5.htm 26-Jun-2013 09:13 1.7M
Rues-78-Yvelines-6.htm 26-Jun-2013 09:13 1.7M
Rues-78-Yvelines-7.htm 26-Jun-2013 09:13 1.7M
Rues-78-Yvelines-8.htm 26-Jun-2013 09:12 1.7M
Rues-78-Yvelines-9.htm 26-Jun-2013 09:12 1.7M
Rues-78-Yvelines-10.htm 26-Jun-2013 09:12 1.7M
Rues-78-Yvelines-11.htm 26-Jun-2013 10:24 1.5M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 08:06 2.1M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 17:39 2.2M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 17:40 2.1M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 17:53 2.2M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 17:52 2.2M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 17:52 2.2M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 18:05 2.2M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 18:15 2.2M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 18:00 2.2M
Rues-92-Hauts-de-Sei..> 03-Jul-2013 08:06 2.3M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:55 1.6M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:55 1.6M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:55 1.6M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:54 1.6M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:54 1.6M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:54 1.6M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:54 1.6M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:53 1.6M
Rues-93-Seine-Saint-..> 04-Jul-2013 09:53 1.6M
Rues-78000-Versaille..> 26-Jun-2013 07:45 1.7M
Rues-78000-Versaille..> 26-Jun-2013 07:45 1.7M
Rues-78000-Versaille..> 26-Jun-2013 07:45 1.7M
Rues-78000-Versaille..> 26-Jun-2013 07:45 1.7M
Rues-78000-Versaille..> 26-Jun-2013 07:44 1.7M
Rues-78000-Versaille..> 26-Jun-2013 08:42 1.7M
Rues-Abbaye.htm 30-May-2013 18:33 616K
Rues-Aerodrome.htm 03-Jun-2013 06:59 1.5M
Rues-Aeroport.htm 30-May-2013 18:32 1.2M
Rues-Aire.htm 05-Jun-2013 16:22 2.5M
Rues-Alain.htm 03-Jun-2013 07:00 1.8M
Rues-Allee-1.htm 30-May-2013 18:35 1.0M
Rues-Ancien.htm 03-Jun-2013 06:54 1.9M
Rues-Arcade.htm 05-Jun-2013 16:23 1.9M
Rues-Artisan.htm 30-May-2013 18:30 1.8M
Rues-Auto.htm 05-Jun-2013 16:22 2.5M
Rues-Avenue-1.htm 30-May-2013 18:35 1.1M
Rues-Avenue-2.htm 03-Jun-2013 07:02 2.9M
Rues-Bas.htm 04-Jun-2013 12:52 2.5M
Rues-Batiment.htm 03-Jun-2013 06:57 1.9M
Rues-Belle.htm 04-Jun-2013 12:57 3.0M
Rues-Bernard.htm 05-Jun-2013 16:28 3.0M
Rues-Bis.htm 26-Jun-2013 07:25 1.4M
Rues-Blanc.htm 04-Jun-2013 12:58 2.6M
Rues-Bleu.htm 04-Jun-2013 12:58 2.6M
Rues-Bois.htm 03-Jun-2013 06:57 2.3M
Rues-Boulevard-1.htm 30-May-2013 18:35 791K
Rues-Boulevard-2.htm 30-May-2013 18:35 771K
Rues-Boulevard-3.htm 26-Jun-2013 07:25 1.6M
Rues-Bourg-2.htm 30-May-2013 18:30 1.4M
Rues-Bourg.htm 30-May-2013 18:32 1.2M
Rues-Bout.htm 04-Jun-2013 12:55 3.1M
Rues-Bra-Commence-pa..> 26-Jun-2013 07:25 1.6M
Rues-Bre-Commence-pa..> 26-Jun-2013 07:24 1.6M
Rues-Bri-Commence-pa..> 26-Jun-2013 07:24 1.6M
Rues-Bru-Commence-pa..> 26-Jun-2013 07:24 1.6M
Rues-Ca-Commence-par..> 26-Jun-2013 07:31 1.7M
Rues-Camp.htm 04-Jun-2013 12:56 3.1M
Rues-Carrefour.htm 05-Jun-2013 16:25 3.1M
Rues-Ce-Commence-par..> 26-Jun-2013 07:28 1.7M
Rues-Centre.htm 05-Jun-2013 16:25 3.1M
Rues-Champ.htm 03-Jun-2013 06:58 1.7M
Rues-Chapelle.htm 03-Jun-2013 06:54 1.9M
Rues-Chateau.htm 03-Jun-2013 06:54 2.2M
Rues-Chem.htm 26-Jun-2013 07:26 2.7M
Rues-Chemin-1.htm 30-May-2013 18:36 873K
Rues-Chemin-2.htm 30-May-2013 18:36 1.0M
Rues-Chemin-3.htm 30-May-2013 18:36 1.0M
Rues-Chemin-4.htm 30-May-2013 18:35 859K
Rues-Cite.htm 03-Jun-2013 06:58 1.8M
Rues-Clot.htm 05-Jun-2013 16:26 3.1M
Rues-Cour.htm 04-Jun-2013 13:02 2.6M
Rues-Court.htm 03-Jun-2013 06:59 1.8M
Rues-Croix.htm 30-May-2013 18:31 1.2M
Rues-Culture.htm 05-Jun-2013 16:24 3.1M
Rues-De-Gaulle.htm 03-Jun-2013 07:02 2.8M
Rues-Departements-01..> 30-May-2013 07:10 2.9M
Rues-Departements-05..> 30-May-2013 07:29 2.7M
Rues-Departements-09..> 30-May-2013 07:28 2.9M
Rues-Departements-13..> 30-May-2013 07:35 3.4M
Rues-Departements-17..> 30-May-2013 07:43 3.0M
Rues-Departements-21..> 30-May-2013 07:56 3.3M
Rues-Departements-25..> 30-May-2013 18:27 3.1M
Rues-Departements-29..> 30-May-2013 18:28 4.0M
Rues-Ecole.htm 03-Jun-2013 06:54 2.0M
Rues-Eglise.htm 03-Jun-2013 06:55 1.8M
Rues-Eugene.htm 30-May-2013 18:32 1.0M
Rues-Faubourg-1.htm 30-May-2013 18:35 601K
Rues-Ferme.htm 04-Jun-2013 13:02 2.7M
Rues-Gare-2.htm 03-Jun-2013 06:59 1.5M
Rues-Gare.htm 30-May-2013 18:33 615K
Rues-Gendarmerie.htm 30-May-2013 18:31 1.0M
Rues-General.htm 30-May-2013 18:30 1.3M
Rues-Grand.htm 26-Jun-2013 07:25 1.4M
Rues-Grande-Rue.htm 30-May-2013 18:31 1.0M
Rues-Hameau.htm 04-Jun-2013 12:52 2.7M
Rues-Haras.htm 26-Jun-2013 07:26 2.7M
Rues-Haut-2.htm 05-Jun-2013 16:32 2.7M
Rues-Haut.htm 04-Jun-2013 12:54 1.8M
Rues-Hotel.htm 03-Jun-2013 06:57 1.9M
Rues-Impasse.htm 30-May-2013 18:33 1.5M
Rues-Jardin.htm 03-Jun-2013 06:58 1.8M
Rues-Joseph.htm 05-Jun-2013 16:21 2.5M
Rues-La-Commence-par..> 26-Jun-2013 07:23 1.7M
Rues-Lac.htm 04-Jun-2013 12:59 2.5M
Rues-Le-Bois.htm 30-May-2013 18:32 639K
Rues-Le-Commence-par..> 26-Jun-2013 07:23 2.4M
Rues-Leclerc.htm 03-Jun-2013 06:59 1.8M
Rues-Lieu.htm 03-Jun-2013 06:57 2.1M
Rues-Lo-Commence-par..> 26-Jun-2013 07:27 2.3M
Rues-Lotissement.htm 04-Jun-2013 13:01 3.2M
Rues-Lu-Commence-par..> 26-Jun-2013 07:27 1.8M
Rues-Ma-Commence-par..> 26-Jun-2013 07:22 1.5M
Rues-Mai-Commence-pa..> 26-Jun-2013 07:22 2.5M
Rues-Mairie.htm 30-May-2013 18:31 1.0M
Rues-Maison.htm 03-Jun-2013 06:52 2.4M
Rues-Marais.htm 04-Jun-2013 12:59 2.5M
Rues-Marie.htm 04-Jun-2013 12:53 1.8M
