As the Internet technology becomes a major information infrastructure, an emerging problem is the tremendous increase of malicious computer intrusions. The present Intrusion Detection System (IDS) serves a useful purpose for detecting such intrusions, but the current situation requires more active response mechanism other than simple detection. This paper describes a multi-agent based tracing system against the intruders when the system is attacked. The focus of the study lies on the secure communication mechanism for the agent message communication. We have extended parameters on the KQML protocol, and apt)lied the public key encryption approach, The limitation might be the requirements of two-way authentication for every communication through the broker agent. This model ma)r not improve the efficiency, but it provides a concrete secure communication. Also this is one important factor to protect the agent and the tracing server during the tracing process.