Abstract: With its wider acceptability, cloud can host a diverse set of data and applications ranging from entertainment to personal to industry. The foundation of cloud computing is based on virtual machines where boundaries among the application data are very thin, and the potential of data leakage exists all the time. For instance, a virtual machine covert timing channel is an aggressive mechanism to leak confidential information through shared components or networks by violating isolation and security policies in practice. The performance of a covert timing channel (covert channel) is crucial to adversaries and attempts have been made to improve the performance of covert timing channels by advancing the encoding mechanism and covert information carriers. Though promising, the redundancy of the covert message is mainly overlooked. This paper applies three encoding schemes namely run-length, Huffman, and arithmetic encoding schemes for data compression of a virtual machine covert timing channel by exploiting redundancy. Accordingly, the paper studies the performance of such channels according to their capacity. Unfortunately, we show that these encoding schemes still contain redundancy in a covert channel scenario, and thereby a new encoding scheme namely optimized Run-length encoding (OptRLE) is presented that greatly enhances the performance of a covert timing channel. Several optimizations schemes adopted by OptRLE are also discussed, and a mathematical model of the behavior of an OptRLE-based covert timing channel is proposed. The theoretical capacity of a channel can be obtained using the proposed model. Our analysis reveals that OptRLE further improves the performance of a covert timing channel, in addition to the effects of the optimizations. Experimental result shows how OptRLE affects the size of covert data and the capacity of covert timing channels, and why the performance of the covert timing channel is improved.