  Runtime predictive analyses enhance coverage of traditional dynamic analyses
based bug detection techniques by identifying a space of feasible reorderings
of the observed execution and determining if any of these witnesses the
violation of some desired safety property. The most popular approach for
modelling the space of feasible reorderings is through Mazurkiewicz's trace
equivalence. The simplicity of the framework also gives rise to efficient
predictive analyses, and has been the de facto means for obtaining space and
time efficient algorithms for monitoring concurrent programs. In this work, we
investigate how to enhance the predictive power of trace-based reasoning, while
still retaining the algorithmic benefits it offers. Towards this, we extend
trace theory by naturally embedding a class of prefixes, which we call strong
trace prefixes. We formally characterize strong trace prefixes using an
enhanced dependence relation, study its predictive power and establish a tight
connection to the previously proposed notion of synchronization preserving
correct reorderings developed in the context of data race and deadlock
prediction. We then show that despite the enhanced predictive power, strong
trace prefixes continue to enjoy the algorithmic benefits of Mazurkiewicz
traces in the context of prediction against co-safety properties, and derive
new algorithms for synchronization preserving data races and deadlocks with
better asymptotic space and time usage. We also show that strong trace prefixes
can capture more violations of pattern languages. We implement our proposed
algorithms and our evaluation confirms the practical utility of reasoning based
on strong prefix traces.
