A multi-level security software architecture includes various components configured to provide full data separation across multiple processors while limiting the number and size of high assurance components. The architecture includes a domain separator for ensuring that messages exchanged between domains that are distributed on different microprocessors are securely routed between domain members. The domain separator verifies a message label including a domain identifier provided by a domain gateway and cryptographically binds the message label to each message via cryptographic keys. This prevents misrouting messages caused by accidental or malicious corruption of message labels. Additionally, the domain separator can encrypt messages as necessary to enforce data separation on shared network buses. The domain separator is also responsible for managing the cryptographic keys used to label or encrypt messages.