Traffic identification is a relevant issue for network operators nowadays. As P2P services are often used as an attack vector, Internet Service Providers (ISPs) and network administrators are interested in modeling the traffic transported on their networks with behavior identification and classification purposes. In this paper, we present a stochastic detection approach, based on the use of Markov models, for classifying network traffic to trigger subsequent security related actions. The detection system works at flow level considering the packets as incoming observations, and is capable of analyze both plain and encrypted communications. After suggesting a general structure for modeling any network service, we apply it to eDonkey traffic classification as a case study.