Abstract This is Part I in a two-part series discussing the development of investigative support for information confidentiality. In this paper, we propose a technique to detect confidential information leakage via protocol-based covert channels based on relation algebra. It provides tests to verify the existence of an information leakage via a monitored covert channel as well as computations which show how the information was leaked if a leakage exists. We also report on a prototype tool that allows for the automation of the proposed technique. Our focus is limited to protocol-based covert channels and instances where covert channel users modulate the sent information by some form of encoding such as encryption.