  Cybercriminals often leverage Bitcoin for their illicit activities. In this
work, we propose back-and-forth exploration, a novel automated Bitcoin
transaction tracing technique to identify cybercrime financial relationships.
Given seed addresses belonging to a cybercrime campaign, it outputs a
transaction graph, and identifies paths corresponding to relationships between
the campaign under study and external services and other cybercrime campaigns.
Back-and-forth exploration provides two key contributions. First, it explores
both forward and backwards, instead of only forward as done by prior work,
enabling the discovery of relationships that cannot be found by only exploring
forward (e.g., deposits from clients of a mixer). Second, it prevents graph
explosion by combining a tagging database with a machine learning classifier
for identifying addresses belonging to exchanges. We evaluate back-and-forth
exploration on 30 malware families. We build oracles for 4 families using
Bitcoin for C&C and use them to demonstrate that back-and-forth exploration
identifies 13 C&C signaling addresses missed by prior work, 8 of which are
fundamentally missed by forward-only explorations. Our approach uncovers a
wealth of services used by the malware including 44 exchanges, 11 gambling
sites, 5 payment service providers, 4 underground markets, 4 mining pools, and
2 mixers. In 4 families, the relations include new attribution points missed by
forward-only explorations. It also identifies relationships between the malware
families and other cybercrime campaigns, highlighting how some malware
operators participate in a variety of cybercriminal activities.
