IP traceback can be used to find the origins and paths of attacking traffic. However, so far, most approaches for IP traceback are hard to be deployed in the Internet because of deployment difficulties. In this paper, we present an incrementally deployable approach based on sampled flows for IP traceback (SampleTrace). In SampleTrace, it is not necessary to deploy any dedicated traceback software and hardware at routers, and an AS-level overlay network is built for incremental deployment. We theoretically analyze the quantitative relation among the probability that a flow is successfully traced back various AS-level hop number, independently sampling probability, and the packet number that the attacking flow comprises. According to Bernoulli's Law of Large Numbers, when a large number of attacking flows are practically traced back in the Internet by SampleTrace, the successfully-traced back relative frequency will approach the successfully-traced back probability.