To investigate the exploitation and contamination by self-propagating Internet worms, a provenance-aware tracing mechanism is highly desirable. Provenance unawareness causes difficulties in fast, accurate identification of a worm?s break-in point, and incurs significant log inspection overhead. This paper presents the design, implementation, and evaluation of process coloring, an efficient provenance-aware approach to worm break-in and contamination tracing. More specifically, process coloring assigns a "color", a unique system-wide identifier, to each remotely-accessible server or process. The color will then be either inherited by spawned child processes or diffused indirectly through process actions (e.g., read/write operations). Process coloring brings two major advantages: (1) It enables fast color-based identification of a worm?s break-in point even before detailed log analysis; (2) It naturally partitions log data based on their colors, effectively reducing the volume of log data that need to be examined for worm investigation. A tamper-resistant log collection method is developed based on the virtual machine introspection technique. Our experiments with a number of real-world worms demonstrate the advantages of processing coloring.