Current taint analyses track flow from sources to sinks, and report
the results simply as source $\to$ sink pairs, or flows. This is imprecise and
ineffective in many real-world scenarios; examples include taint
sources that are mutually exclusive, or flows that combine sources
(e.g., IMEI and MAC Address are concatenated, hashed, leaked vs. IMEI
and MAC Address hashed separately and leaked separately). These
shortcomings are particularly acute in the context of Android, where
sensitive identifiers can be combined, processed, and then leaked, in
complicated ways. To address these issues, we introduce a novel,
{\it algebraic-datatype} taint analysis that generates rich yet concise taint
signatures involving AND, XOR, hashing – akin to algebraic, product
and sum, types. We implemented our approach as a static analysis for
Android that derives app leak signatures – an algebraic
representation of how, and where, hardware/software identifiers are
manipulated before being exfiltrated to the network. We perform six
empirical studies of algebraic-datatype taint tracking on 1,000 top apps from
Google Play and their embedded libraries, including: discerning
between ``raw'' and hashed flows which eliminates a source of
imprecision in current analyses; finding apps and libraries that go
against Google Play's guidelines by (ab)using hardware identifiers;
showing that third-party code, rather than app code, is the
predominant source of leaks; exposing potential de-anonymization
practices; and quantifying how apps have become more privacy-friendly
over the past two years.