Phonotactic Reconstruction of Encrypted VoIP Conversations:
Hookt on fon-iks
Andrew M. White∗ Austin R. Matthews∗†
Kevin Z. Snow∗ Fabian Monrose∗∗ Department of Computer Science† Department of Linguistics
University of North Carolina at Chapel Hill
Chapel Hill, North Carolina{amw, kzsnow, fabian}@cs.unc.edu, armatthe@email.unc.edu

Abstract—In this work, we unveil new privacy threats against
Voice-over-IP (VoIP) communications. Although prior work
has shown that the interaction of variable bit-rate codecs andlength-preserving stream ciphers leaks information, we showthat the threat is more serious than previously thought. In particular, we derive approximate transcripts of encrypted VoIP
conversations by segmenting an observed packet stream into
subsequences representing individual phonemes and classifying
those subsequences by the phonemes they encode. Drawing on
insights from the computational linguistics and speech recognition communities, we apply novel techniques for unmasking
parts of the conversation. We believe our ability to do sounderscores the importance of designing secure (yet efficient)ways to protect the confidentiality of VoIP conversations.

I. I NTRODUCTION
Over the past decade, Voice-over-IP (VoIP) telephony has
witnessed spectacular growth. Today, VoIP is being usedeverywhere, and is making steady headway as a replacement
for traditional telephony in both the residential and commercial sectors. The popularity of free online services such as
Skype, Fring, and Google Talk is a case in point. Indeed,
several analysts predict that VoIP will remain the fastest
growing industry over the next decade, and some forecast
that the subscriber base will top 225 million by 2013.1 Yet,even with this widespread adoption, the security and privacy
implications of VoIP are still not well understood. In fact,even with the attention VoIP security (or lack thereof) has
received in the past, the concerns have mostly centered on
the lack of authenticity in the call setup phases of the signal
and session negotiation protocol(s) or susceptibility to denialof service attacks [33]. Regarding the confidentiality of thedata streams themselves, the prevailing wisdom is that, due
to the open nature of traffic traveling over the Internet, VoIP
packets should be encrypted before transmission.
However, current practices for encrypting VoIP packets have been shown to be insufficient for ensuring privacy. In particular, two common design decisions made in
VoIP protocols—namely, the use of variable-bit-rate (VBR)
codecs for speech encoding and length-preserving stream
1 See, for example, Infonetics Research’s VoIP and UC Services andSubscribers Report at http://www.infonetics.com.

ciphers for encryption—interact to leak substantial information about a given conversation. Specifically, researchers
have shown that this interaction allows one to determine thelanguage spoken in the conversation [55], the identity ofthe speakers [2, 41], or even the presence of known phrases
within the call [56].
Rightfully so, critics have argued that the aforementioned
threats do not represent a significant breach of privacy. For
example, the language of the conversation might easily be
determined using only the endpoints of the call—a callfrom Mexico to Spain will almost certainly be in Spanish.
While the identification of target phrases is more damning,
it still requires the attacker to know (in advance) what she
is looking for within the stream. In this work, we make nosuch assumption about a priori knowledge of target phrases.
Rather, our ultimate goal is to reconstruct a hypothesizedtranscript of the conversation from the bottom up: ourapproach segments the observed sequence of packets into
subsequences corresponding to individual phonemes (i.e.,the basic units of speech). Each subsequence is then classified as belonging to a specific phoneme label, after which
we apply speech and language models to help constructa phonetic transcription of parts of the conversation. To
assess the quality of our reconstruction, we apply widely
accepted translation scoring metrics that are designed to
produce quality scores at the sentence level that correlate
well with those assigned by human judges.
The approach we take has parallels to how infants findwords in a speech stream. As Blanchard et al. [8] point out,
adults effortlessly break up conversational speech into words
without ever realizing that there are no pauses between
words in a sentence. This feat is possible because we havea lexicon of familiar words that we can use to segment theutterance. Infants have no such luxury. Instead, they must
use perceptual, social, and linguistic cues to segment thestream of sounds. Amazingly, the linguistic cues come fromlearned language-specific constraints (or phonotactics) that
determine whether a word is well-formed or not; infants use
this knowledge of well-formedness to help segment speech.
The fascinating problem here is that infants must learn
these rudimentary, language-specific, constraints while si-multaneously segmenting words. They use familiar words(e.g., their own names) to identify new words which aresubsequently added to their small vocabulary. Interestingly,
the Linguistic and Psychological Sciences literature aboundswith studies (e.g., [9, 23]) which show that, as early as
six months of age, infants use knowledge of which basic
phonemes occur together, as well as learned knowledgeof within-word versus between-word sounds, to segment
perceived utterances into words. As we show later, weapply a similar methodology when tackling the problem ofreconstructing words from strings of phonemes.

Backnessɛ 'head'æ 'had'a 'aisle'ʊ 'hood'u 'who'd'o 'go'

ɜ 'heard'

ʌ 'one'ɔ 'hawed'

Heighti 'heed'ɪ 'hid'e 'aid'ɑ 'via'ɒ 'pond'Figure 1. Vowels in American English (IPA format), differentiated bytheir height and backness. Left: the relative tongue positions.

II. BACKGROUND I NFORMATION
Before proceeding further, we first present some necessary
background that is helpful in understanding the remainderof the paper. The background material covers basic notions
in linguistics, pertinent VoIP details, and information about
the datasets we use throughout the paper.

(i.e., whether the shape of the lips is rounded or not). For
example, compare how your mouth feels as you say ‘beat’and ‘boot’. If you hold the vowels in these two words,
you should be able to feel a difference in the backness of
your tongue. Similarly, if you compare the words ‘beat’ and‘bat’, you should feel your chin moving up and down; thisis a difference in height. To feel a difference in rounding,compare the words ‘put’ and ‘pool’. As you say ‘pool’ you
should feel your lips pucker into a round shape; in ‘put’,
your lips should be loose.
Consonants and vowels are combined to make syllables,
which are governed by the phonotactics of the language —that is, language-specific conditions that determine whether aword is well-formed or not. At a high level, phonotactics areconstraints on which phones can follow which, i.e., rules thatgovern how phones may be combined to form well-formed
words. In English, for example, there are strong constraints
on what kinds of consonants can appear together: [st] (asin ‘stop’) is a very common consonant cluster, but someconsonant sequences, like [zdr] (as in ‘eavesdrop’), are notlegal word-initial sequences in English.2
Lastly, in linguistics and speech processing, an abstraction
called a phoneme (typically written between slashes) isused to represent similar phones with a single symbol. For
example, the phoneme /t/ can be pronounced as any of threephones in English; which of these three phones is uttereddepends on the position within a syllable: /t/ is pronounced
as [th ] at the beginning of a syllable (as in ‘top’=[th op’]),[t] in the middle of a syllable (as in ‘stop’=[st6p’]), and[t’] at the end of a syllable (as in ‘pot’ = [ph ot’]). Phones
belonging to the same phoneme are called allophones: [th ],[t], and [t’] are allophones of the phoneme /t/.
In Section V, we leverage such linguistic insights to build
a string matching technique based on phonetic edit distance.
In addition, we use phonotactics of English (e.g., what
sequences of phonemes or allophones are allowable withinwords) to assist with phoneme classification.

Phonetic Models of Speech
The ideas in this paper rely heavily on insights frommodern theories of phonology. In particular, we draw froma vast body of work on phonetics—i.e., the study of linguistic sounds. From a computational perspective, phonetics
involves studying how sound is produced by the articulatorsof the vocal tract and how they are realized acoustically [30].
In phonetics, the pronunciations of words are modeled
as strings of symbols representing individual speech units
called phones. While several alphabets exist for representing
phones (e.g., ARPAbet for American English), the de facto
standard is the International Phonetic Alphabet (IPA).
For the remainder of the paper, what is particularly important is that each phone is based on articulatory processes, andthat phones are divided into two main classes: consonants
and vowels. Both kinds of sounds are formed by the motionof air through the mouth, throat and nose. Consonants, forexample, are made by restricting airflow in some way, andcan be both voiced (meaning they involve vibrations of
the vocal cords) or unvoiced. By contrast, vowels usually
involve less obstruction of air flow, and are louder and longer
lasting than consonants. Moreover, because all consonants
are sounds made by restricting airflow, they can be distinguished from each other by where the restriction is made(the place of articulation) as well as how the restriction ismade (the manner of articulation). In English, for example,
the “hissing” sound of [f ] in ‘fish’ is made by pressing
the lower lip against the upper teeth. There are several
major manners (e.g., stops, nasals, and fricatives) used to
distinguish consonants.
Likewise, vowels can also be characterized by articulatory
processes (see Figure 1), the most important of which arevowel height (i.e., roughly the height of the highest part of
the tongue), backness (i.e., roughly indicating where the tipof the tongue is relative to the vocal track), and roundness

2 Of course, [zdr] may exist word-initially in other languages, such as in
the Bulgarian word [zdraf], which means ‘health’.

2

codecs to minimize bandwidth usage while maintaining
call quality. Under VBR, the size of the codebook entry,
and thus the size of the encoded frame, can vary basedon the complexity of the input frame. The specificationfor Secure RTP (SRTP) [3] does not alter the size of theoriginal payload; thus encoded frame sizes are preserved
across the cryptographic layer. The size of the encrypted
packet therefore reflects properties of the input signal; it isexactly this correlation that our approach leverages to model
phonemes as sequences of lengths of encrypted packets.

Voice over IP
In VoIP, voice data and control messages are typicallytransmitted through separate channels. The control channel
generally operates using an application-layer protocol, suchas the Extensible Messaging and Presence Protocol (XMPP)
used by Google Talk or the Session Initiation Protocol(SIP). The voice channel typically consists of a Real-time
Transport Protocol (RTP) stream transmitted over UDP. We
concern ourselves only with the voice channel in this work.
Typically, the audio for VoIP conversations is encodedusing an audio codec designed specifically for speech, such
as Skype’s SILK, the Enhanced Full Rate (EFR) codec specified by the GSM standard, or the open-source Speex usedin many VoIP applications (including Google Talk). Speech
codecs differ from general audio codecs since human speech
can be represented much more efficiently than general audio
due to the periodic nature of certain speech signals and therelatively limited number of potential sounds. For speech,
sound is usually sampled at between 8 and 32 kHz (i.e.,
between 8,000 and 32,000 samples are recorded per second).
This sample stream is then segmented into frames, or blocks,of a certain duration and each frame is compressed by the
speech codec for transmission. The duration is a fixed value
generally between 10 and 100ms; a typical value, and theone used in this work, is 20ms, which corresponds to 320
samples per frame when sampling at 16kHz.
Many modern speech codecs are based on variants of awell-known speech coding scheme known as code-excited
linear prediction (CELP) [49], which is in turn based on thesource-filter model of speech prediction. The source-filter
model separates the audio into two signals: the excitation
or source signal, as produced by the vocal cords, and theshape or filter signal, which models the shaping of the soundperformed by the vocal tract. This allows for differentiationof phonemes; for instance, vowels have a periodic excitation
signal while fricatives (such as the [sh] and [f] sounds) havean excitation signal similar to white noise [53].
In basic CELP, the excitation signal is modeled as an entry
from a fixed codebook (hence code-excited). In some CELP
variants, such as Speex’s VBR mode, the codewords canbe chosen from different codebooks depending on the complexity of the input frame; each codebook contains entries
of a different size. The filter signal is modeled using linear
prediction, i.e., as a so-called adaptive codebook where thecodebook entries are linear combinations of past excitation
signals. The “best” entries from each codebook are chosen
by searching the space of possible codewords in orderto “perceptually” optimize the output signal in a process
known as analysis-by-synthesis [53]. Thus an encoded frame
consists of a fixed codebook entry and gain (coefficient) forthe excitation signal and the linear prediction coefficients forthe filter signal.
Lastly, many VoIP providers (including Skype) use VBR

III. H IGH - LEVEL OVERVIEW OF O UR A PPROACH
The approach we pursue in this paper leverages the correlation between voiced sounds and the size of encrypted packets observed over the wire. Specifically, we show that one
can segment a sequence of packet sizes into subsequences
corresponding to individual phonemes and then classify
these subsequences by the specific phonemes they represent. We then show that one can segment such a phonetictranscript on word boundaries to recover subsequences ofphonemes corresponding to individual words and map thosesubsequences to words, thereby providing a hypothesizedtranscript of the conversation.
Rock and roll!

VoIP Conversation Reconstruction Process

Encrypted VoIP Packets

Packet Lengths

Phoneme
Segmentation

Phoneme Segments

PhonemeClassificationr ɒ k æ m d r oPhonemesiCorrected Phonemes

rock

æ-n-d

Word Segments

and

Words

➋

l

Language Model
Correctionr ɒ k æ n d r o ʊ
r-ɒ-k

➊

l
Word
Segmentation➌

Word
Classification➍r-o-ʊ-lroll

Figure 2. Overall architecture of our approach for reconstructing transcripts
of VoIP conversations from sequences of encrypted packet sizes.

Our work draws from advances in several areas of computational science. A simplified view of our overall process
is shown in Figure 2. As an example, we use the phrase‘rock and roll’, the dictionary pronunciation for which isrepresented as [ô6k ænd ôoUl] in IPA. Our basic strategy is asfollows. First, we use a maximum entropy model (Stage Ê)3

to segment the sequence of packet sizes into subsequences
corresponding to individual phonemes. We then apply (StageË) a combination of maximum entropy and profile hidden
Markov models to classify each subsequence of packet
sizes according to the phoneme the subsequence represents,
resulting in an approximate phonetic transcript of the spoken
audio. In our example, this transcript is [ô6kæmdôoil].
The hypothesized transcript is improved by applying
a trigram language model over phonemes (and phoneme
types) which captures contextual information, such as likely
phoneme subsequences, and corrects the transcript to represent the most likely sequence of phonemes given boththe classification results and the language model. In our
example, this results in [ô6kændôoUl]. Notice the unlikely
phonetic sequence [æmd] has been replaced with the far
more likely [ænd]. Next, we segment (Stage Ì) the resulting
transcript into subsequences of phonemes corresponding toindividual words using a phonetic constraint model, resulting
in the more recognizable string [ô6k ænd ôoUl].
Finally, we match each subsequence to the appropriate English word using a phonetic edit distance metric (Stage Í),
giving us the desired ‘rock and roll’. In the general case, atrigram language model over words (and parts-of-speech) isthen applied to the resulting transcript to correct tense anddisambiguate between homophones (i.e., words which soundalike) by finding the most likely sequence of words given
both the hypothesized transcript and the language model.

encoder, instrumented to output the sizes of the encodedframes, in wideband (i.e., 16kHz) VBR mode. The phonetic
labels from the time-aligned transcripts are then used to
identify subsequences corresponding to individual phonemes
for training; this encoding process gives us a number ofsequences for each phoneme.
We note that the approach we take assumes that theadversary has access to (i) the sequence of packet lengths
for an encrypted VoIP call (ii) knowledge of the language
spoken in the call, (iii) representative example sequences(or models derived therefrom) for each phoneme, and (iv) aphonetic dictionary. The first assumption can be readily met
through any number of means, including the use of a simple
packet sniffer. Knowledge of the language of interest can begleaned using the ideas in [32, 55] or by simple endpoint
analysis. Lastly, obtaining representative example sequences
for each phoneme is fairly straightforward: one can use
prerecorded, phonetically-labeled audio files as input to aspeech codec to produce the examples. In fact, using labeled
examples from prerecorded audio is exactly the approach
we take in this paper in order to model phonemes. Note thatour primary goal is to build speaker-independent models andthus we do not require speaker-specific audio. Finally, phonetic dictionaries (e.g., CELEX, CMUdict and PRONLEX)
are readily available; we use data from TIMIT and from the
PRONLEX dictionary (containing pronunciations from over
90,000 words) as our phonetic dictionary.
IV. R ELATED W ORK

Data and Adversarial Assumptions

Traffic analysis of encrypted network communications has
a long and rich history. Much of that work, however, isfocused on identifying the application protocol responsible
for a particular connection (e.g., [7, 12, 17, 31, 42, 43, 54]).
It was not until recently that researchers [10, 38, 48, 50, 52]
began exploring techniques for inferring sensitive information within encrypted streams using only those features thatremain intact after encryption—namely packet sizes andtiming information. Song et al. [50], for example, used theinter-arrival time between packets to infer keystrokes in SSH
sessions; Sun et al. [52] and Liberatore and Levine [38]showed that identification of web sites over encrypted HTTP
connections (e.g., SSL) is possible using the sizes of theHTML objects returned by HTTP requests; Saponas et al.
[48] showed how to identify the movie being watched overan encrypted connection.
More pertinent to this paper, however, is the work of
Wright et al. [55, 56] that showed that encrypted VoIP calls
are vulnerable to traffic analysis wherein it may be possible
to infer the spoken language of the call or even the presenceof certain phrases. In the latter case, the approach of Wrightet al. assumes that the objective is to search an encrypted
packet stream for subsequences matching a target phrase
or word, such as ‘attack at dawn’, and therefore requiresthat a probabilistic model of likely corresponding packet

The TIMIT Acoustic-Phonetic Continuous Speech Corpus [21], a collection of recorded speech with time-aligned
word and phonetic transcripts (allowing us to label segmentsby phoneme), provides the audio samples used in our experiments. The TIMIT corpus is comprised of 6,300 speechrecordings from 630 speakers representing eight major dialects of American English. Each speaker reads ten predetermined, phonetically-rich sentences, such as ‘Alimony
harms a divorced man’s wealth’, ‘The drunkard is a social
outcast’, and ‘She had your dark suit in greasy wash water all
year’. The transcripts contain labels for 58 distinct phonemelevel3 sounds. Following the standard approach used in
the speech recognition community, we folded the original
TIMIT classes into 45 labels [36] by combining some allophones and combining closures and silences. ARPAbet, thephonetic alphabet on which the labeling systems of TIMIT
is based, does not map directly to the articulatory featuresin Section II; therefore, we convert the phoneme sequences
to their IPA representations for the latter stages of ourevaluation. In order to generate sequences of encoded frame
lengths from the (16kHz, single-channel) audio samples, we
encode each sample using the reference version of the Speex
3 In addition to phonemes, the corpus contain some labels for sounds,
such as pauses and recording errors, unrelated to human speech.

4length sequences (i.e., representing the target phrase in its
entirety) be generated in advance. As discussed earlier, nosuch a priori information is necessary under our approach:we construct transcripts from the bottom up rather thanmatching phrases from the top down.
Several other approaches for exploring information leakage in encrypted VoIP calls (working under different environmental assumptions than Wright et al.) have also been
proposed. For example, if silence suppression is assumed(i.e., packet transmission is suppressed when a party issilent), researchers posit that the duration of talk spurts forwords spoken in isolation makes identification of specific“speeches” [37, 41] possible. In a recent study with 20
speakers, Backes et al. [2] show that speaker-specific pause
patterns might be sufficient to undermine the anonymityof speakers in encrypted VoIP calls. That said, it is well
accepted in the speech community that continuous speech(i.e., everyday communication) lacks identifiable pauses
between words [11]. In fact, speakers generally talk faster(and typically shorten or run sentences together) as speech
becomes more natural and colloquial. This observation iseven more important in our context where there are no
within-word pauses. Hence, we make no assumptions about
voice activation detection and/or silence suppression.
Lastly, Dupasquier et al. [15] investigate the extent of
information leakage from Skype voice traffic. The authors
conclude that the general concept we pursue here “seems
quite difficult” because classification of phonemes is too
challenging. Thus, they revert to the prior setting of knowing
the target phrase in advance and use dynamic time warpingto validate the work of Wright et al. A focus of this paper
is showing that such statements were premature, and thatphoneme-level reconstruction can be successful in undermining the privacy of encrypted VoIP conversations.
For conciseness, the relevant literature on speech andlanguage models will be presented elsewhere in this paper.

the filter signal. As mentioned earlier, the filter signal fora given frame is modeled as a linear combination of past
excitation signals. Thus more information must be encoded
for frames in which the sound changes drastically—suchas at the transition between two phonemes. Similarly, lessinformation is encoded for intra-phoneme frames, where
the sound changes relatively little. Figure 3 illustrates howchanges in frame size can indicate a phonetic boundary.
official

deadline

Frame Size (bytes)

an

ɛ n ɪ

f

ɪ

ʃ

l

d

ɛ

d

l

a

n

Figure 3. Frame size sequence for the first few words of an utterance of ‘anofficial deadline cannot be postponed’, illustrating how the sizes of framesdiffer in response to phoneme transitions. Notice the distinct changes (e.g.,a sharp rise) in frame sizes near some phoneme boundaries (e.g., [I], [f],and [S] in ‘official’). Near other phoneme boundaries (e.g., [d], [l], and [a]in ‘deadline’), however, frame size remains constant.

Methodology
To perform the segmentation, we apply a probabilistic
learning framework known as maximum entropy modeling4 [6, 28] that simultaneously captures many contextual
features in the sequence of frames, as well as the history of classifications in the sequence, to decide whichframes represent phoneme boundaries. Such models havebeen successfully applied to problems like part-of-speechtagging [46] and text segmentation [5].
Maximum entropy modeling estimates the posterior probability p(y|x), where x is an observation and y a label.
In order to do so, one calculates the empirical distributionp̃(x, y) from training data as the relative frequency of
examples with value x and label y. One then defines binary
indicator functions, f (x, y), to describe features of the data
relevant to classification.
In the case of phonetic boundary segmentation, we represent a given frame with w. The labels, i.e., boundary orinterior frame, are represented by the binary variable v. An
indicator function f (w, v) then describes a feature of theframe which is relevant to whether that frame represents aphoneme boundary, for example:1,
if v is boundary and w has size n,f (w, v) =0,otherwise.

V. OVERALL M ETHODOLOGY
We now turn our attention to explaining the details behind
the key ideas explored in this paper. Wherever possible, we
provide the intuition that drives our design decisions.
A. Finding Phoneme Boundaries (Stage Ê)Given the sequence of packet sizes from a VoIP conversation, the first challenge is to identify which of thesepackets represent a portion of speech containing a boundary
between phonemes. While automatic segmentation of speech
waveforms on phonetic boundaries has received much attention in the speech recognition community, in our context
we have no access to the acoustic information and must
operate on the sequence of packet sizes. However, recall
that many speech codecs, and Speex in particular, are basedon CELP (code-excited linear prediction), which encodes
speech with two different signals: the excitation signal and4 Also known as multinomial logistic regression.

5Given an indicator function, one can compute the expectedvalue of a feature, f , with respect to the training data as:Xp̃(f ) =p̃(x, y)f (x, y)Instantiation of
Feature Template 6
frame
trigramx,yOne can thus represent any statistical phenomena in the
training data with p̃(f ). The expected value of f with respect
to the target model, p(y|x), may be represented as:Xp(f ) =
p̃(x)p(y|x)f (x, y)Sequence of Frames

framesequence

last boundary

x,y

wi

Instantiation of
Feature Template 8
number of

Requiring that p̃(f ) = p(f ) imposes the constraint that themodel agree with the training data with respect to featuref ; over all features, this yields a set of constraints for thetarget model:
C = p ∈ P | p(fi ) = p̃(fi ) for i ∈ {1, 2, · · · , n}framesFigure 4. Classification example for current frame, wi . The label for wi
is dependent on a number of features, including the frame size sequencesince the last hypothesized boundary (shown here in gray). An example
feature derived from each of templates 6-8 is depicted on the right handside.

Many models may satisfy the set of constraints. However,the principle of maximum entropy states that the model thatbest represents the data given the current state of knowledge
is the one with the most entropy. This yields a constrained
optimization problem of the form argmaxp∈C H(p), where
H(p) is the entropy of y conditioned on x in the model p.
1
2
3
4
5
6
7
8

Instantiation of
Feature Template 7

are not detectable by frame size changes (such as the longsequence of same-sized frames in Figure 3), we also modelfeatures such as phoneme length (feature template 8).
To efficiently solve the optimization problem posed by
maximum entropy modeling, we use the megam frameworkwith the limited memory BGFS [39] algorithm to obtain themodel p(w|v). Having built a model, we estimate the probability of each frame, in order, being a phoneme boundaryby evaluating the estimated posterior p(w|v). Since featuretemplates 7 and 8 depend on previously classified labels,
we use a dynamic programming algorithm to maximize thelikelihood of the sequence as a whole rather than greedily
selecting the most likely label for each frame. The algorithm,
a beam search, stores a list of the l most likely candidate
segmentations up to the current frame; this list is updated
after each frame is evaluated. We choose as our final
segmentation the most likely candidate at the last frame.

Phoneme Segmentation Feature Templates
size of frame wi (i.e., the current frame size)
size of frame wi−1 (i.e., the previous frame size)
size of frame wi+1 (i.e., the next frame size)
bigram of sizes for frames wi−1 , wibigram of sizes for frames wi , wi+1
trigram of sizes for frames wi−1 , wi , wi+1
sequence of frame sizes since the last hypothesized boundary
number of frames since since the last hypothesized boundary

Table IF EATURE TEMPLATES FOR THE PHONETIC SEGMENTATION , WHERE wi
REPRESENTS THE i TH FRAME .

For boundary identification, we define several feature templates which specify features that we hypothesize correlatewith phoneme boundaries. The templates we use are given
in Table I, and some features are illustrated in Figure 4 forclarity. Although each frame only gives us one observablefeature (namely, the size of the frame), we leverage thesurrounding frames, and the history of previously classified
frames, in the sequence to create a much richer feature set.
The templates are used to automatically generate the fullfeature set directly from the data.
As per our hypothesis regarding the interaction between
linear prediction and frame size, notice that feature templates
1-6 capture the frame sizes in the proximity of the current
frame. The frame size unigrams, bigrams, and trigrams must
be explicitly captured because maximum entropy models
do not model feature interactions, i.e., they only consider
individual features in isolation. Some phonemes may always
exhibit a certain frame size sequence; we capture this behavior with feature template 7. Lastly, because some boundaries

Evaluation
In order to provide rigorous assessments of our methodology, we perform cross-validation in the segmentation andclassification stages of our experiments. Cross-validation isa method for estimating the generalization performance of aclassifier by partitioning the available data into complementary subsets, training with one subset, and testing with theother. In particular, we perform k-fold cross-validation, in
which the data is partitioned into k complementary subsets.
For each fold, one subset is selected for testing and theremainder used for training. The training and testing are
performed as many times as there are subsets, with eachacting as the testing set in one fold. The results of all iterations are then averaged to give the expected generalization
performance, which mitigates the possibility of experimental
6

we explicitly exclude the transition frames in the phonemeclassification stage that follows. Finally, for the remainder ofthis paper we make the simplifying assumption that phoneme
boundaries can be recognized correctly; this assumption isrevisited in Section VI.

results being unduly influenced by fortuitous selection oftraining and testing data.
To evaluate the performance of our phonetic segmentation
model, we perform a 5-fold cross-validation experiment
for each dialect in the TIMIT corpus. Using a holdout
set of female speakers from the New England dialect, we
experimentally determined an optimal value of 8 for the
beam width l. We report the performance using precision(i.e., the fraction of boundaries in the transcription that arepresent in the reference transcription) and recall (i.e., thefraction of boundaries in the reference that appear in thetranscription) as our metrics.
Dialect
New England
Northern
North Midland
South Midland
Southern
New York City
WesternArmy Brat

n=1
Precision
Recall
0.85390.72330.85550.73320.85090.73720.84520.70860.85250.70370.85300.70960.85860.72590.84650.7540

B. Classifying Phonemes (Stage Ë)
We remind the reader that our overall approach requiresthat we segment a sequence of encrypted packet lengths
into subsequences corresponding to individual phonemes,
and then classify these subsequences based on empiricalmodels derived from labeled training data. We therefore havea classification problem where the classes of interest are thevarious phonemes.
For classification, we employ a combination of two systems: one context-dependent, wherein the labeling of asegment is dependent on the labelings of its neighbors, andanother context-independent, wherein a single segment is
considered in isolation. We combine these two approaches
in order to leverage the strengths of each. Our contextdependent classifier is also based on maximum entropy modeling, while the context-independent classifier is based on
profile hidden Markov modeling. Profile HMMs have beenused widely in both the biological sequence analysis [16]and speech recognition communities [29].
Aside from the ability to incorporate contextual information, maximum entropy modeling is discriminative. Discriminative models are often used for classification tasks because
they model only the parameters of interest for classificationand thus can often encode more information. Hidden Markov
models, on the other hand, are generative models. Generativemodels are sometimes preferable to discriminative models
because they model the entire distribution over examples
for a given class rather than just the information necessary
to discriminate one class from another.
To combine the two models, we utilize a form of Bayesianinference to update the posterior given by the maximum
entropy classifier with the “evidence” given by the profile
HMM classifier. The updated posterior is then passed to alanguage model, as described below. By utilizing both typesof models we enjoy increased classification accuracy whileproviding input to the language model with a valid statisticalinterpretation. Next, we discuss each stage in turn.

n=2
Precision
Recall
0.94430.87350.94580.88370.94020.89010.93520.86270.94050.8586
0.93860.86280.94390.86520.93890.8985

Table IIP HONETIC SEGMENTATION PERFORMANCE FOR EACH DIALECT IN THE
TIMIT CORPUS .

While interpreting these results, we note that Raymond
et al. [47] have shown that phoneme boundaries are inexact
even at the frame level—in fact, in their study, humantranscribers agreed (within 20ms) on less than 80% of theboundaries. For this reason, a frame classified as a boundary
is considered as correct if it occurs within n frames of an
actual boundary; likewise, it is incorrect if there are no actual
boundaries within n frames. Table II summarizes, for eachdialect, our segmentation performance for n = 1 and n = 2.
For the sake of comparison, we also note that state-of-the-art
classifiers (operating on the raw acoustic signal) are able torecall approximately 80% (again, within 20ms) of phoneme
boundaries in TIMIT [18, 44] with error rates similar to ourown. Unfortunately, the comparison is not direct: our labels
are necessarily at the granularity of frames (each 20ms),
rather than samples, which means that the within-n-frame
requirement for agreement is looser than the within-20ms
requirement.
The results in Table II show that our performance ison par with these other techniques. More importantly, theimprecision in the transcription boundaries does not negatively impact the performance of the next stage of ourapproach since the frames in question, i.e., the beginningand ending frames of each phoneme, are precisely those thatwill contribute the most variance to a phoneme model. In
other words, the transition frames are likely to incorporatea significant amount of noise, due to their proximity to surrounding phonemes, and are therefore unlikely to be usefulfor classifying phonemes. It is for exactly this reason thatMaximum Entropy Discrimination of Phonemes
We discriminate between phonemes in a manner similar to the segmentation process described in Section V-A.
Specifically, we define a new set of feature templates oversequences of phonemes (which are themselves composedof sequences of frame sizes). For pedagogical reasons, thespecifics are given in Table III and an example feature isillustrated in Figure 5.
Feature templates 1-3 capture the exact frame sequence ofthe current and surrounding phonemes to identify phonemes
7Profile HMM Modeling of Phonemes

Sequence of Phonemes

contains contains

To provide generative models of the various phonemes,
we train a profile HMM for each. A profile HMM is ahidden Markov model with a specific topology that encodesa probability distribution over finite sequences of symbols
drawn from some discrete alphabet. In our case, the alphabet
is the different sizes at which a speech frame may be
encoded; in Speex’s wideband VBR mode, there are 19 suchpossibilities. Given the topology of a hidden Markov model,
we need to estimate the parameters of the model for each
set of sequences. Towards this end, we utilize a well-known
algorithm due to Baum et al. [4] that iteratively improves themodel parameters to better represent the example sequences.

qi

Most Frequently Observed Trigramsin Training Corpus

Classification

Figure 5. An example instantiation of feature template 10 which illustrates
how the template models the presence of common trigrams.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

To label an observed sequence of packet sizes, we find theposterior probability p(r|q), where q represents the observed
sequence of frame sizes, for each class label r. For the
standalone maximum entropy classifier, the output for agiven observation and label is an estimate of the desiredquantity. For the profile HMM classifier, we calculate, using
Bayesian inference, the posterior p(r|q) = p(r)p(q|r) using
the likelihood5 p(q|r), given by the profile HMM. This “updates” a prior probability p(r) with the new “evidence” fromthe profile HMM. For the stand-alone classifier evaluation,
we estimate the prior p(r) as the proportion of examples
belonging to the class in our training data. When using
both the profile HMM and maximum entropy classifiers inconjunction, we use the estimated p(r|q) from the maximum
entropy model as the prior p(r). In all cases, we choose thelabel whose model has the maximum posterior probability
as the predicted label for a given sequence. These posterior
probabilities also give a probability distribution over candidate labels for each phoneme in an utterance; these serve as
the language model input.

Phoneme Classification Feature Templates
qi (i.e., the current phoneme’s frame size sequence)qi−1 (i.e., the previous phoneme’s frame size sequence)
qi+1 (i.e., the next phoneme’s frame size sequence)qi , excluding the first and the last frames
qi−1 , excluding the first and the last frames
length of qi (in frames)
length of qi−1 (in frames)
frequency of frame size n in qi
bigram b of frame sizes is in qi , for top 100 bigrams
trigram t of frame sizes is in qi , for top 100 trigrams
bigram b of frame sizes is in qi−1 , for top 100 bigrams
trigram t of frame sizes is in qi−1 , for top 100 trigrams
bigram b of frame sizes is in qi+1 , for top 100 bigrams
trigram t of frame sizes is in qi+1 , for top 100 trigrams

Table IIIF EATURE TEMPLATES FOR THE MAXIMUM ENTROPY PHONEMECLASSIFIER . W E DENOTE AS qi THE SEQUENCE OF FRAME SIZES FOR
THE i TH PHONEME .W E LIMIT THE NUMBER OF n- GRAMS TO 100 FOR
PERFORMANCE REASONS .

Enhancing Classification using Language Modelingthat frequently encode as exactly the same frame sequence.
Feature templates 4 and 5 encode similar information, but
drop the first and last frames in the sequence in accordancewith our earlier hypothesis (see Section V-A) that the
beginning and ending frames of the phoneme are the mostvariable. Feature templates 6 and 7 explicitly encode thelength of the current and previous phonemes since some
types of phonemes are frequently shorter (e.g., glides) or
longer (e.g., vowels) than others. Feature template 8 captures
the frequency of each possible frame size in the current
sequence. Feature templates 9-14 encode the presence ofeach of the 100 most frequent frame size bigrams or trigrams
observed in the training data; we limit the number of bigramsand trigrams to maintain manageable run-time performance.
Finally, since we later incorporate high-level contextual
information (such as neighboring phonemes) explicitly witha language model, we do not attempt to leverage that
information in the classification model.

Lastly, in order to incorporate contextual information
on surrounding phonemes, we apply a trigram language
model using the SRILM language modeling toolkit [51].
In particular, we train a trigram language model over bothphonemes and phoneme types (e.g., vowels and stops).
We disambiguate between candidate labels by finding the
maximum likelihood sequence of labels given both the estimated distributions output by the classifier and the phonetic
language model.
Evaluation
Our preliminary results show that we can correctly classify 45% of phonemes in a 10-fold cross-validation experiment on the New England dialect.6 For this experiment,
5 The likelihood given by an HMM is scaled by the marginal p(q).

6 For brevity, we omit the other dialects as the results do not differ
significantly.

8we operate on input with perfectly segmented phonetic
boundaries so as to provide a baseline for our classifiers
when evaluated independently from the other stages in our
method. As can be seen from Figure 6, the combination of
the profile HMM and maximum entropy classifiers with thelanguage model outperforms the individual classifiers.
While this classification performance might sound lackluster, these results are quite surprising given the limited
context we operate under (i.e., packet sizes only). For
instance, recent approaches working directly on the acoustic
signal report 77% accuracy on the TIMIT dataset in thecontext-dependent case (which corresponds roughly to ourapproach after application of the language model). In thecontext-independent case (analogous to our profile HMM
classification approach without the language model), accuracy rates as high as 67% have been achieved [26] on the
TIMIT dataset. Similarly, expert human transcribers achieverates only as high as 69% [36].

actual boundaries, we match the surrounding phonemes withall possible phonemes and pairs of phonemes which canbegin or end words, and remove potential word breaks which
would result in invalid word beginnings or endings.
We then perform an additional step whereby we use apronunciation dictionary to find valid word matches for
all contiguous subsequences of phonemes. For each such
subsequence, we insert word breaks at the positions that areconsistent across all the matches. For example, suppose thesequence [InOIliôæg] (‘an oily rag’) has the following threepossible segmentations:◦ [In OIli ôæg] (‘an oily rag’)◦ [In OIl i ôæg] (‘an oil E. rag’)◦ [In O Il i ôæg] (‘an awe ill E. rag’)Since these choices have two words in common, we
segment the phrase as [In OIli ôæg].
Dialect
New England
Northern
North Midland
South Midland
Southern
New York City
WesternArmy Brat

Precision
0.72510.75030.76530.72340.72720.74410.72980.7277

Recall
0.85120.85220.85690.85120.84550.86500.84190.8461

Table IVW ORD B REAK I NSERTION P RECISION AND R ECALL

The results of a 10-fold cross-validation experiment are
given in Table IV. Overall, we achieve average precision andrecall of 73% and 85%, respectively. Very recent results,
however, by Blanchard et al. [8] and Hayes and Wilson[25] suggest that accuracy above 96% can be achieved using
more advanced techniques than implemented here. Due totime and resource constraints, we make the simplifying
assumption that word breaks can be correctly recognized.
We revisit this assumption in Section VI.

Figure 6. Phoneme classification accuracy on the New England dialect forthe profile HMM and maximum entropy classifiers alone, in combination,
and with the language model applied.

C. Segmenting Phoneme Streams into Words (Stage Ì)

D. Identifying Words via Phonetic Edit Distance (Stage Í)

In this stage, our task is to identify likely word boundaries
from the stream of classified phonemes. To do so, we follow
the methodology suggested by Harrington et al. [24] that,
until very recently, was among the best approaches for wordboundary identification. We also extend their approach toincorporate an additional step that makes use of a pronunciation dictionary.
Harrington et al. identify word breaks with a two-stepprocess. The first step consists of inserting potential word
breaks into the sequence of phonemes in positions that would
otherwise produce invalid phonemic triples, i.e., triples that
do not occur within valid words in English. Each such identified triple then causes the insertion of a pair of potential
word breaks, one between each pair of phonemes in the
triple. To resolve which of the potential word breaks are

The final task is to convert the subsequences of phonemes
into English words. To do so, we must identify words
that best match the pronunciation dictated by the recovered
phonemes. Towards this end, we design a novel metric ofphonetic distance based on the difference in articulatory features (i.e., the associated physiological interactions discussed
in Section II) between pairs of phonemes. Our approach hassome similarities to ideas put forth by Oakes [45], whichitself builds upon the work of Gildea and Jurasky [22] andZobel and Dart [58, 59]. Oakes [45] proposes a phoneticallybased alignment algorithm, though there is no notion ofrelative distance between various places or manners ofarticulation. In Zobel and Dart [59], the distances between
phonemes are handcrafted, and their matching algorithm
considers only the single most likely pronunciation.
9

To compare two sequences of phonemes, we use theLevenshtein distance with insertions and deletions weighted
at one unit and edits weighted according to their phonetic
distance as defined above. Table V gives example wordcomparisons along with their primary differences (in termsof articulartory processes).
In order to determine the optimal values for the insertionand deletion weights for our phonetic edit distance metric,
we performed a simple parameter space exploration. We
hypothesized that the absolute insertion and deletion costs
were less significant than the difference between them. As
such we tuned based on two parameters, base cost and offset.
Each insertion costs the base cost plus half the offset andeach deletion costs the base cost minus half the offset. The
effectiveness of each set of parameters is shown in Figure 8.
Somewhat surprisingly, a base cost of 1.0 and offset of
0.0 (corresponding to insertion and deletion weights of 1.0)
provided the highest average word accuracy.

In our approach, we define the distance between a vowel
and a consonant as one unit, with a few exceptions: weassign a cost of 0 for converting an [i] to a [j] (or viceversa) as well as for converting a [u] to a [w]. We do so
because [w] and [j] are what are known as semi-vowels, andare essentially very short realizations of their corresponding
vowels. Moreover, we assign a cost of 0 for [R] (i.e., flap‘r’) and [t], as well as for [R] and [d]. This is because [R]is an allophone of [t] and [d]. Hence, we would like suchminor phonetic alterations to have little effect on the distance
between two pronunciations.

w

Approximant

0.32

MannerSibilant

0.27

Fricative

f

0.05

θ

17.2

Stop

17.1

Interdental

Velar

Word Accura

Labiodental

Glottal

17.0

Place

cy

16.9

Figure 7.

Illustration of distance between consonants [f], [T], and [w].
16.8

To measure the distance between two vowels or two
consonants, we use three different articulatory features asaxes and calculate the Euclidean distance (see Figure 7)
between the points corresponding to the two phonemes(scaled to a maximum of one unit). For consonants thesefeatures are voice, manner, and place of articulation. For
vowels they are rounding, backness and height. Thus we
differentiate between substitution of a phonetically similar
segment, such as replacement of [s] (as in ‘see’) by [S] (asin ‘she’), or of a completely different segment, such as of[s] (as in ‘seen’) with [k] (as in ‘keen’).
Word 1bæt ‘bat’bit ‘beat’
did ‘deed’
b2t ‘but’
b2t ‘but’bid ‘bead’
f6D3~ ‘father’hUkt ‘hooked’
hEloU ‘hello’

Word 2mæt ‘mat’bæt ‘bat’bid ‘bead’
bOt ‘bought’bæt ‘bat’bit ‘beat’m2D3~ ‘mother’
f6nIks ‘phonics’
w3~ld‘world’Phonetic
Distance
0.07220.10420.10500.12500.12670.57740.7292
2.95733.1811

0.0

1.0
0.2

1.2
0.4
Of
fse 0.6
t

1.4
1.6
0.8

se
Ba

1.8
1.0

2.0

Figure 8. Parameter space exploration, in terms of average word accuracy,
for our phonetic edit distance.

To match a sequence of phonemes to an English word,
we compute the phonetic distance between the sequence andeach pronunciation in our dictionary in order to obtain a listof the closest pronunciations to the sequence. However, theexistence of homophones means that, even if the pronunciation is correct, we may have many choices for the word
spoken. For example, ‘ate’ and ‘eight’ are indistinguishable
phonetically: both are pronounced [eIt].
In order to disambiguate between homophones, we incorporate a word and part-of-speech based language model
to choose between the candidate words using contextual
information from the sentence as a whole. Thus we candisambiguate between ‘ate’ and ‘eight’ by finding the most
likely part of speech (e.g., noun, verb, pronoun, or adverb)
for that position in the sentence. Using the SRILM language

Primary
Difference
mannerheightplace
rounding
backnessvoicing
n/a
n/a
n/a

Table VE XAMPLES OF OUR P HONETIC E DIT D ISTANCE BETWEEN PAIRS OF
EXAMPLE WORDS . T HE LAST COLUMN LISTS THE PRIMARYDIFFERENCE ( IN TERMS OF ARTICULATORY PROCESSES ).

10

modeling toolkit, we train a trigram language model overboth words and parts-of-speech on the well-known Brown
corpus [20]. The part of speech tags used are those currently implemented in NLTK [40]. To improve the abilityof the language model to disambiguate between candidate
words, we assign each word a weight which estimates theconditional probability of the observed pronunciation given
the candidate word.
To find these weights, we need a measure of how likely
an observed pronunciation is given the phonetic distanceto the actual pronunciation of the given word; therefore,
we estimate the cumulative distribution function (CDF)
over phonetic distances by deriving an empirical CDF (seeFigure 9) from the distances of a large number of pronunciation pairs. We then transform the given distance between
pronunciations into a probability estimate by evaluating theempirical CDF at that distance. For each pronunciation in thecandidate list for an observed word, we weight the associatedwords with the probability estimate for that pronunciation.7
Thus we have, for each word in an utterance, a list of
candidate words with associated conditional probability estimates. Disambiguation is performed by finding the maximum likelihood sequence of words given the candidates,
their probability estimates, and the language model.

E. Measuring the Quality of Our Output
Since the early 1990s, much work has gone into finding
appropriate metrics for scoring machine transcriptions fromautomatic speech recognition and transcription systems. In
that context, the main task is to generate a literal transcription of every word that is spoken. The closer the machinetranscription is to a human translation, the better it is. Early
approaches for automatically measuring such performance
simply relied on examining the proportion of word errors
between the actual and transcribed conversations (i.e., theWord Error Rate (WER)), but WER has been shown to bea poor indicator of the quality of a transcript since good
performance in this context depends not only on the amountof errors, but also on the types of errors being made. For
example, from the perspective of human interpretation, it
often does not matter if the transcribed word is ‘governed’
instead of ‘governing’.
Hence, modern automatic scoring systems reward candidate text based on the transcription’s adequacy (i.e., howwell the meaning conveyed by the reference transcription
is also conveyed by the evaluated text) and fluency (i.e.,
the lengths of contiguous subsequences of matching words).
To date, many such scoring systems have been designed,with entire conferences and programs dedicated solely to this
topic. For instance, NIST has coordinated evaluations under
the Global Autonomous Language Exploitation (GALE)
program since the mid-nineties. While the search for better
metrics for translation evaluation remains an ongoing challenge, one widely accepted scoring system is the METEOR
Automatic Metric for Machine Translation by Lavie andDenkowski [35]. METEOR was designed to produce quality
scores at the sentence level which correlate well with those
assigned by human judges. We evaluate the quality of ourguesses using METEOR; for concreteness, we now review
pertinent details of that scoring system.
Lavie and Denkowski’s method evaluates a hypothesizedtranscription by comparison with a reference transcription.
The two transcripts are compared by aligning first exact
word matches, followed by stemmed word matches, andfinally synonymous word matches. The alignment is performed by matching each unigram string in the referencetranscription to at most one word in the hypothesis transcription. To compute the score from such an alignment, letm be the number of matched unigrams, h the number of
unigrams in the hypothesis, and r the number of unigramsin the reference. The standard metrics of unigram precision(P = m/h) and recall (R = m/r) are then computed.
Next, the parameterized f -score, i.e., the harmonic meanof P and R given a relative weight (α) on precision, is
computed:

1.0

Percentile

0.8
0.6
0.4
0.2
0.0

0

Figure 9.

1234Phonetic Edit Distance

5

6

Empirical CDF of phonetic edit distance.

At this point, the observant reader will have surely notedthat the overall process is fundamentally inexact because,in the end, some sort of human judgement is required toevaluate the hypothesized output. That is, we need some way
to measure the quality of our guesses, say, as assessed bya human judge who compares them to the actual transcript.
Thankfully, the closely related problem of scoring machinetranslations has been extensively studied. In what follows,
we discuss how we measure the accuracy of our guesses.

Fmean =

7 A word which is associated with multiple pronunciations is weighted

according to the closest pronunciation, i.e., we take the maximum weightof all associated weights for the given word.

P ∗R.
α ∗ P + (1 − α) ∗ R

To penalize hypotheses which have relatively long sequences
11terances.8 Except where explicitly specified, all experiments
are 10-fold cross-validation experiments and are performed
independently on each dialect. As discussed in Section V,
for these experiments we assume that the segmentation ofphonemes is correct to within human transcriber tolerances.
However, the effects of this assumption are specificallyexamined in a small experiment described separately below.

of incorrect words, Lavie and Denkowski count the number
c of ‘chunk’ sequences of matched unigrams which are
adjacent, and in the correct order in the hypothesis. A fragmentation penalty is then computed as Pf rag = γ ∗ (c/m)β ,where γ and β are parameters determining the maximum
penalty and relative impact of fragmentation, respectively.
The final METEOR score is then calculated as Sm =(1 − Pf rag ) ∗ Fmean for each hypothesis.

cliff
was
soothedbyaluxurious
massageAB• cliff• was• soothed
• by

it's
that ◦ that's
• not
you
your
easy
headache • headache• to• create◦ illuminating• examples

isnotexcepttothecreate• luxurious illuminated• massage
examplesMETEOR Score:
0.78

METEOR Score:
0.53

SA1:“She had your dark suit in greasy wash water all year.”She had year dark suit a greasy wash water all year.
She had a dark suit a greasy wash water all year.
She had a dark suit and greasy wash water all year.
SA2:“Don’t ask me to carry an oily rag like that.”
Don’t asked me to carry an oily rag like that.
Don’t ask me to carry an oily rag like dark.
Don’t asked me to carry an oily rag like dark.

C

Score
0.67
0.67
0.67
Score
0.98
0.82
0.80

Table VI
T OP SCORING HYPOTHESES FROM THE N EW E NGLAND DIALECT.

METEOR Score:
0.18

Figure 11 shows the distributions of METEOR scores
under each of the dialects for the two content-dependent
experiments. For SA1, the results are fairly tightly groupedaround a score of 0.6. The SA2 scores show significantly
more variance; while some hypotheses in this case wererelatively poor, others attained perfect scores. To ease interpretation of the scores, we provide the three highest-scoring
hypotheses for each sentence, along with their scores, inTable VI. In addition, recall that sentences with scores over
0.5 are generally considered understandable in the machinetranslation context; 91% of our SA1 reconstructions and
98% of our SA2 reconstructions exceed this mark.
The independent case, on the other hand, proves to be amore challenging test for our methodology. However, we arestill able to reconstruct a number of sentences that are easilyinterpretable by humans. For instance, Table VII shows thefive highest-scoring hypotheses for this test on the New
England dialect. In addition, a number of phrases within
the sentences are exactly correct (e.g., ‘the two artists’). For
completeness, we note that only 2.3% of our reconstructions
score above 0.5. However, the average score for the top
10% (see Figure 12) is above 0.45. That said, we remind
the reader that no reconstruction, even a partial one, should
be possible; indeed, any cryptographic system that leaked
as much information as shown here would immediately bedeemed insecure.
To mitigate any concern regarding our two previous
simplifying assumptions, namely, the accurate segmentationof frame size sequences on phoneme boundaries and of(noisy) phoneme sequences on word boundaries, we perform
one final experiment. We believe sufficient evidence has
been given to show that we can accomplish these tasks
in isolation; however, one possible critique stems from the

Figure 10. Example scoring of three hypothesized guesses. For each, thehypothesized guess is on the left, with the reference on the right. Filled
circles represent exact matches. Hollow circles show matches based onstemming.

Denkowski and Lavie [13] performed extensive analysis
to determine appropriate values for the parameters α, β,and γ which optimize the correlation between METEOR
score and human judgments. In our experiments, we use
the parameter set that is optimized to correlate with the
Human Targeted translation Edit Rate (HTER) metric forhuman judgement on the GALE-P2 dataset [14]. We disable
synonym matching as our system does no semantic analysis,
and thus any such matches would be entirely coincidental.
Some examples are shown in Figure 10. Notice that even asingle error can result in scores below 0.8 (e.g., in part (a)).
Moreover, in some cases, a low score does not necessarily
imply that the translation would be judged as poor by ahuman (e.g., one can argue that the translation in part (c)is in fact quite decent). Finally, Lavie indicates that scores
over 0.5 “generally reflect understandable translations” andthat scores over 0.7 “generally reflect good and fluent
translations” in the context of machine translation [34].
VI. E MPIRICAL E VALUATIONIn the analysis that follows, we explore both contentdependent and content-independent evaluations. In bothcases, we assume a speaker-independent model wherein we
have no access to recordings of speech by the individual(s)involved in the conversation. In the content-dependent case,
we perform two experiments, each incorporating multiple
different utterances of a particular sentence. We use TIMIT’s
SA1 and SA2 sentences for these experiments because eachis spoken exactly once by each of the 630 speakers, providing a rare instance of sufficient examples for evaluation. In
the content-independent case, we incorporate all TIMIT ut-

8 We follow the standard practice in the speech recognition community
and use the SA1 and SA2 sentences for training only.

12

METEOR Score

1.0
0.8
0.6
0.4
0.2
0.0

New England

Northern

North Midland

South Midland

Southern

New York City

WesternArmy Brat

WesternArmy Brat(a) SA1: “She had your dark suit in greasy wash water all year.”

METEOR Score

1.0
0.8
0.6
0.4
0.2
0.0

New England

Northern

North Midland

South Midland

Southern

New York City(b) SA2: “Don’t ask me to carry an oily rag like that.”
Figure 11.

METEOR scores for all hypothesized transcripts of sentences SA1 and SA2 for each dialect in the TIMIT dataset.

Hypothesis
À Codes involves the displacement of aim.
Á The two artists instance attendants.
Â Artificial intelligence is carry all.
Ã Bitter unreasoning dignity.
Ä Jar, he whispered.

Reference Sentence
Change involves the displacement of form.
The two artists exchanged autographs.
Artificial intelligence is for real.
Bitter unreasoning jealousy.
Honey, he whispered.

METEOR Score
0.57
0.49
0.49
0.47
0.47

Table VII
T HE FIVE HIGHEST SCORING HYPOTHESES FROM THE N EW E NGLAND DIALECT UNDER THE CONTENT- INDEPENDENT MODEL .

potential effects, when these assumptions are lifted, on theefficacy of the methodology as a whole. Thus we remove
these assumptions in a small, content-independent experiment comprised of the audio samples spoken by female
speakers in the “Army Brat” dialect of the TIMIT corpus.
The average score for the top 10%, in this case, is 0.19, witha high score of 0.27. We remind the reader that even such
low scoring hypotheses can be interpretable (see Figure 10),and we stress that these results are preliminary and that
there is much room for improvement—in particular, recently
proposed techniques can be directly applied in our setting(see Section V-C). Moreover, there are opportunities forextensions and optimizations at every stage of our approach,including, but not limited to, weighting the influence of thedifferent classification and language models. In addition,other scoring systems for machine translation exist (e.g.,
NIST and BLEU), which may be appropriate in our context.
We plan to explore these new techniques, optimizations andmetrics in the future.

able to construct an accurate transcript of every sentenceuttered during a conversation. Therefore, she must havesome way to measure her confidence in the output generated,and only examine output with confidence greater than somethreshold. To show this can be done, we define one suchconfidence measure, based on our phonetic edit distance,
which indicates the likelihood that a given transcript isapproximately correct.
Our confidence measure is based on the notion thatclose pronunciation matches are more likely to be correct
than distant matches. We use the mean of the probability
estimates for each word in a given hypothesized transcript as
our confidence value for that hypothesis. Analysis indicatesthat this confidence measure correlates (see Figure 13)
with the maximum METEOR score obtained from the 10
best hypotheses output by the word-level language model(Stage Í). This implies that, given a set of training datasuch as the TIMIT dataset, an adversary can determine anappropriate threshold for the calculated confidence values
to suit her preference as to the balance between precisionand recall in the hypothesized transcripts. The results in
Figure 14 provide one such analysis under the contentdependent model. We note that the threshold reduces the setof hypotheses to a subset with improved METEOR scores.

A. An Adversarial Point of View (Measuring Confidence)Due to the difficult nature of our task (i.e., numerous
factors influencing phonetic variation and the fact that we
operate on encrypted data), an adversary is unlikely to be
13

METEOR Score

1.0
0.8
0.6
0.4
0.2
0.0

New England
Figure 12.

Northern

North Midland

South Midland

Southern

New York City

WesternArmy Brat

The top 10% of METEOR scores for hypothesized transcripts under the content-independent assumption.

METEOR Score

1.0
0.8
0.6
0.4
0.2
0.0

New England(37/49)Northern(73/102)

North Midland(85/102)

South Midland(70/100)

Southern(65/98)

New York City
(39/46)

Western(81/100)

Army Brat(24/33)Figure 14. METEOR scores for hypothesized transcripts for sentence SA2 with confidence values above the threshold of .90 for each dialect in the
TIMIT dataset. The number of transcripts with confidence values above the threshold compared to the total for each dialect is shown in parentheses.

words for which we have high confidence. Preliminary
results indicate that such “masking” may provide benefits
to interpretation, for example, outputting ‘nonprofit ? all? ? raisers’ instead of ‘nonprofit organizations all swiftly
fairy raisers’ as the hypothesis for ‘nonprofit organizations
have frequent fund raisers’. We forego such analysis at thistime since the METEOR metric does not allow for unknown
words—an automated method of evaluating such hypotheses
is necessary before we can make any claims.

0.8
0.7
METEOR Score

0.6
0.5
0.4
0.3
0.2
0.1

B. Discussion & Mitigation
We note, like other work in this area (e.g., [2, 37, 41, 55,56]), that we assume each packet contains a single frame.
However, some recently designed codecs, such as Skype’s
new codec (dubbed SILK), can vary the number of frames
per packet based on network conditions. It therefore remains
to be seen if the approach outlined herein can be adapted tothat setting; exploring that, however, requires a substantial
data collection effort that is beyond the scope of this work.
Further, our experiments assume that packets are observedin correct order and are not fragmented or combined, i.e.,
the adversary can observe packets at the level of the local
network (e.g., between VoIP endpoint and hub or PBX) or
can perform IP defragmentation or TCP stream reassembly.
The inherently limited fidelity of the channel, however,suggests that our technique would be robust to reasonablenoise in the form of packet reordering and fragmentation.
Lastly, a knee-jerk reaction to thwarting this and otheraforementioned threats to VoIP is to simply use constant
bit-rate codecs or block ciphers. However, variable bitrate encoded audio encrypted under a block cipher with a

0.0
0.76 0.78 0.80 0.82 0.84 0.86 0.88 0.90 0.92 0.94
Confidence Value

Figure 13. Scatter plot of METEOR scores against our confidence values(Pearson’s r-value of 0.43).

Unfortunately, the correlation of this particular confidence
metric does not extend well to the content-independent
model. However, we note that there are many other methods
to measure confidence which an adversary could leverage,
including those based on the posteriors output by the classification stage, the likelihoods given by the language models,and ex post facto analysis of the well-formedness (in termsof syntax, i.e., grammar) of the hypotheses. We hope to
explore these strategies in the near future.
In closing, we note that one could also apply the notionof confidence values to interpreting the results at the word,rather than the sentence, level. In particular, we could filter
our hypotheses at the word-level by only outputting those14

small block size is theoretically vulnerable to our attack.
Packet sizes in that scenario still correlate with input signals,
albeit at a reduced fidelity; thus relatively large block sizes
are necessary to ensure privacy. For this reason, the useof constant bit-rate codecs is important to consider as analternative to simple block ciphers for VoIP, since such
codecs might improve call quality given a relatively large
fixed packet size. Another alternative might even be to dropor pad packets [19, 27, 57], though, in that case, the effect onperceived call quality is unclear. We note, however, that VoIP
providers have made no move to employ any such measures:
Skype’s SILK, for instance, is a VBR codec. Similarly, oneof the leading proposals for 4G, the LTE Advanced standard,
specifies a VBR codec for audio [1] and the use of SRTP
to secure voice data channels.

[3] M. Baugher, D. McGrew, M. Naslund, E. Carrara, and K. Norrman. The secure real-time transport protocol (SRTP). RFC
3711, Internet Engineering Task Force, 2004.
[4] L. E. Baum, T. Petrie, G. Soules, and N. Weiss. A maximization technique occurring in the statistical analysis ofprobabilistic functions of Markov chains. The Annals of
Mathematical Statistics, 41(1):164–171, 1970.
[5] D. Beeferman, A. Berger, and J. Lafferty. Statistical models
for text segmentation. Mach. Learn., 34(1-3), 1999.
[6] A. L. Berger, S. A. D. Pietra, and V. J. D. Pietra. A
maximum entropy approach to natural language processing.
Computational Linguistics, 22:39–71, 1996.
[7] L. Bernaille and R. Teixeira. Early recognition of encrypted
applications. In PAM, pages 165–175, 2007.
[8] D. Blanchard, J. Heinz, and R. Golinkoff. Modeling thecontribution of phonotactic cues to the problem of word
segmentation. The Journal of Child Language, 37(3):487–
511, 2010.
[9] H. Bortfeld, J. Morgan, R. Golinkoff, and K. Rathbun.
Mommy and me: Familiar names help launch babies into
speech-stream segmentation. Psychological Science, 16:298–
304, 2005.
[10] S. Chen, R. Wang, X. Wang, and K. Zhang. Side-channelleaks in web applications: A reality today, a challenge tomorrow. In Proceedings of the IEEE Symposium on Security
and Privacy, pages 191–206, 2010.
[11] R. A. Cole and J. Jakimik. A Model of Speech Perception,
chapter 6, pages 133–163. Lawrence Erlbaum Associates,
1980.
[12] M. Crotti, M. Dusi, F. Gringoli, and L. Salgarelli. Trafficclassification through simple statistical fingerprinting. SIGCOMM Comput. Commun. Rev., 37(1):5–16, 2007.
[13] M. Denkowski and A. Lavie. Choosing the right evaluation
for machine translation: an examination of annotator andautomatic metric performance on human judgment tasks. In
Proceedings of AMTA, 2010.
[14] M. Denkowski, A. Agarwal, S. Banerjee, and A. Lavie. The
METEOR MT Evaluation System, Version 1.2. Carnegie
Mellon University, Pittsburgh, PA, 2010.
[15] B. Dupasquier, S. Burschka, K. McLaughlin, and S. Sezer.
Analysis of information leakage from encrypted Skype conversations. International Journal of Information Security,
pages 1–13, 2010.
[16] R. Durbin, S. Eddy, A. Grogh, and G. Mitchison. BiologicalSequence Analysis: Probabilistic Models of Proteins andNucleic Acids. Cambridge University Press, 1998.
[17] M. Dusi, M. Crotti, F. Gringoli, and L. Salgarelli. Detection of
encrypted tunnels across network boundaries. In ICC, pages
1738–1744, 2008.
[18] A. Esposito and G. Aversano. Text independent methods forspeech segmentation. In Nonlinear Speech Modeling andApplications, volume 3445 of Lecture Notes in Computer
Science, pages 261–290. Springer, 2005.
[19] P. Fogla, M. Sharif, R. Perdisci, O. Kolesnikov, and W. Lee.
Polymorphic blending attacks. In Proceedings of the USENIX
Security Symposium, pages 241–256, 2006.
[20] W. N. Francis and H. Kucera. Brown corpus manual. Technical report, Department of Linguistics, Brown University,
1979.
[21] J. S. Garofolo, L. F. Lamel, W. M. Fisher, J. G. Fiscus, D. S.
Pallett, N. L. Dahlgren, and V. Zue. TIMIT acoustic-phonetic
continuous speech corpus, 1993.
[22] D. Gildea and D. Jurasky. Learning bias and phonologicalrule induction. Computational Linguistics, 22(4):497–530,

VII. C ONCLUSION
In this paper, we explore the ability of an adversary toreconstruct parts of encrypted VoIP conversations. Specifically, we propose an approach for outputting a hypothesized transcript of a conversation, based on segmenting
the sequence of observed packets sizes into subsequences
corresponding to the likely phonemes they encode. Thesephoneme sequences are then mapped to candidate words,
after which we incorporate word and part-of-speech based
language models to choose the best candidates using contextual information from the hypothesized sentence as a whole.
Our results show that the quality of the recovered transcripts
is far better in many cases than one would expect. While thegeneralized performance is not as strong as we would have
liked, we believe the results still raise cause for concern:in particular, one would hope that such recovery would not
be at all possible since VoIP audio is encrypted precisely toprevent such breaches of privacy. It is our belief that withadvances in computational linguistics, reconstructions of thetype presented here will only improve. Our hope is that thiswork stimulates discussion within the broader community
on ways to design more secure, yet efficient, techniques forpreserving the confidentiality of VoIP conversations.
VIII. ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their insightfulcomments. We also thank Elliott Moreton of the Departmentof Linguistics at UNC-Chapel Hill for helpful suggestions.
This work is supported in part by NSF grants CCF-1017318
and CNS-0852649.
R EFERENCES[1] 3GPP. Extended adaptive multi-rate wideband (AMR-WB+)
codec. Technical Report 26.290, 3rd Generation Partnership
Project (3GPP), 2009.
[2] M. Backes, G. Doychev, M. Dürmuth, and B. Köpf. Speakerrecognition in encrypted voice streams. In Proc. 15th European Symposium on Research in Computer Security, pages
508–523, 2010.

15

clustering using machine learning techniques. In PAM, pages
205–214, 2004.
[44] I. Mporas, T. Ganchev, and N. Fakotakis. Speech segmentation using regression fusion of boundary predictions.
Computer Speech & Language, 24(2):273–288, 2010.
[45] M. Oakes. Computer estimation of vocabulary in protolanguage from word lists in four daughter languages. Journal of
Quantitative Linguistics, 7(3):233–243, 2000.
[46] A. Ratnaparkhi. A maximum entropy model for part-ofspeech tagging. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 133–142,
1996.
[47] W. D. Raymond, M. Pitt, K. Johnson, E. Hume, M. Makashay,
R. Dautricourt, and C. Hilts. An analysis of transcription
consistency in spontaneous speech from the Buckeye corpus.
In Proceedings of the International Conference on Spoken
Language Processing, 2002.
[48] T. S. Saponas, J. Lester, C. Hartung, S. Agarwal, andT. Kohno. Devices that tell on you: privacy trends in consumer ubiquitous computing. In Proceedings of the USENIX
Security Symposium, pages 1–16, 2007.
[49] M. R. Schroeder and B. S. Atal. Code-excited linear prediction (CELP): High-quality speech at very low bit rates.
In Proceedings of the IEEE International Conference on
Acoustics, Speech, and Signal Processing, volume 10, pages
937–940, April 1985.
[50] D. X. Song, D. Wagner, and X. Tian. Timing analysis of
keystrokes and timing attacks on SSH. In Proceedings of the
USENIX Security Symposium, pages 25–25, 2001.
[51] A. Stolcke. SRILM – an extensible language modeling
toolkit. In Proceedings of the ICSLP, volume 2, pages 901–
904, 2002.
[52] Q. Sun, D. R. Simon, Y.-M. Wang, W. Russell, V. N. Padmanabhan, and L. Qiu. Statistical identification of encrypted
web browsing traffic. In Proceedings of the IEEE Symposium
on Security and Privacy, 2002.
[53] J.-M. Valin. The Speex codec manual, 2007.
[54] C. V. Wright, F. Monrose, and G. M. Masson. On inferring
application protocol behaviors in encrypted network traffic.
Journal of Machine Learning Research, 6:2745–2769, 2006.
[55] C. V. Wright, L. Ballard, F. Monrose, and G. M. Masson.
Language identification of encrypted VoIP traffic: Alejandray Roberto or Alice and Bob? In Proceedings of the USENIX
Security Symposium, 2007.
[56] C. V. Wright, L. Ballard, S. E. Coull, F. Monrose, and G. M.
Masson. Spot me if you can: Uncovering spoken phrases inencrypted VoIP conversations. In Proceedings of the IEEE
Symposium on Security and Privacy, 2008.
[57] C. V. Wright, S. E. Coull, and F. Monrose. Traffic morphing:An efficient defense against statistical traffic analysis. In
Proceedings of the Network and Distributed System Security
Symposium, 2009.
[58] J. Zobel and P. Dart. Finding approximate matches in large
lexicons. Software—Practice and Experience, 25(3):331–345,
1995.
[59] J. Zobel and P. Dart. Fnetik: An integrated system forphonetic matching, 1996. RMIT, Technical Report 96-6.

1996.
[23] M. Halle. Knowledge unlearned and untaught: What speakers
know about the sounds of their language. Linguistic Theory
and Psychological Reality, pages 294–303, 1978.
[24] J. Harrington, G. Watson, and M. Cooper. Word boundary
identification from phoneme sequence constraints in automatic continuous speech recognition. In Computational
linguistics - Volume 1, pages 225–230, 1988.
[25] B. Hayes and C. Wilson. A maximum entropy model ofphonotactics and phonotactic learning. Linguistic Inquiry, 39(3):379–440, 2008.
[26] Y. Hifny and S. Renals. Speech recognition using augmented
conditional random fields. IEEE Transactions on Audio,
Speech, and Language Processing, 17(2):354 –365, 2009.
[27] A. Iacovazzi and A. Baiocchi. Optimum packet length
masking. In 22nd International Teletraffic Congress (ITC),
pages 1–8, 2010.
[28] E. T. Jaynes. Information theory and statistical mechanics.
Phys. Rev., 106(4):620–630, May 1957.
[29] F. Jelinek. Statistical Methods for Speech Recognition.
Massachusetts Institute of Technology, 1997.
[30] D. Jurafsky and J. H. Martin. Speech and Language Processing: An Introduction to Natural Language Processing,Computational Linguistics, and Speech Recognition. Prentice
Hall, 2008.
[31] T. Karagiannis, K. Papagiannaki, and M. Faloutsos. BLINC:
multilevel traffic classification in the dark. SIGCOMM Comput. Commun. Rev., 35(4):229–240, 2005.
[32] T. Kempton and R. K. Moore. Language identification:
Insights from the classification of hand annotated phonetranscripts. In Speaker and Language Recognition Workshop,
Jan. 2008.
[33] A. D. Keromytis. A survey of Voice over IP security
research. In Proceedings of the 5th International Conferenceon Information Systems Security, pages 1–18, 2009.
[34] A. Lavie. Evaluating the output of machine translation
systems. AMTA Tutorial, 2010.
[35] A. Lavie and M. J. Denkowski. The METEOR metricfor automatic evaluation of machine translation. MachineTranslation, 23:105–115, September 2009.
[36] K.-F. Lee and H.-W. Hon. Speaker-independent phoneme
recognition using hidden Markov models. The Journal of
the Acoustical Society of America, 84(S1):62, 1988.
[37] T. Leila and R. Bettati. Privacy of encrypted Voice-overIP. In Proceedings of the IEEE International Conference on
Systems, Man and Cybernetics, pages 3063 –3068, 2007.
[38] M. Liberatore and B. N. Levine. Inferring the sourceof encrypted HTTP connections. In Proceedings of the
ACM Conference on Computer and Communications Security,
pages 255–263, 2006.
[39] D. C. Liu, J. Nocedal, and D. C. On the limited memory
BFGS method for large scale optimization. Mathematical
Programming, 45:503–528, 1989.
[40] E. Loper and S. Bird. NLTK: The natural language toolkit,
May 2002.
[41] Y. Lu. On traffic analysis attacks to encrypted VoIP calls.
Master’s thesis, Cleveland State University, Fenn College ofEngineering, 2009.
[42] G. Maiolini, A. Baiocchi, A. Iacovazzi, and A. Rizzi. Real
time identification of SSH encrypted application flows byusing cluster analysis techniques. In Proceedings of theInternational IFIP-TC 6 Networking Conference, pages 182–
194, 2009.
[43] A. McGregor, M. Hall, P. Lorier, and J. Brunskill. Flow16