On-line monitoring is a useful technique for ensuring system reliability. By continuously supervising the system's operation, a wide range of problems, such as physical defects, transient faults and design errors, can be detected. A monitor M*'s behavior can be viewed as an abstraction of the target system M's behavior, and can be represented by a homomorphic mapping from M to M*. We present a systematic procedure to select homomorphisms and measure their costs. Experimental results are also presented which quantify some basic trade-offs between area overhead and fault coverage.