Capacity estimation is an important part of covert channel analysis. It measures the severity of a covert channel by estimating the maximum information rate attainable over it. Traditional capacity estimation methods usually calculate the channel capacity based on a synchronous model, assuming that the channel is synchronous or there are mechanisms that can be utilized to synchronize the transmission. The overhead for synchronization is ignored.

In this paper we argue that covert channels in general are non-synchronous and the overhead for synchronization is not negligible. Instead of assuming a synchronous model, we propose to use the deletion-insertion channel as a more general basis of capacity estimation. Capacity estimation is extended to be able to evaluate the overhead for overcoming non-synchronous effects. Our study shows that reliable communication over a non-synchronous channel is still possible even without synchronization mechanisms. Such non-synchronized communications, however, are not as effective as the synchronized ones. The capacity degradation due to the non-synchronous effects is derived. A tight upper bound of the capacity of synchronized channels is also given.