  Relational verification encompasses information flow security, regression
verification, translation validation for compilers, and more. Effective
alignment of the programs and computations to be related facilitates use of
simpler relational invariants and relational procedure specs, which in turn
enables automation and modular reasoning. Alignment has been explored in terms
of trace pairs, deductive rules of relational Hoare logics (RHL), and several
forms of product automata. This article shows how a simple extension of Kleene
Algebra with Tests (KAT), called BiKAT, subsumes prior formulations, including
alignment witnesses for forall-exists properties, which brings to light new
RHL-style rules for such properties. Alignments can be discovered
algorithmically or devised manually but, in either case, their adequacy with
respect to the original programs must be proved; an explicit algebra enables
constructive proof by equational reasoning. Furthermore our approach inherits
algorithmic benefits from existing KAT-based techniques and tools, which are
applicable to a range of semantic models.
