The trend in Multi-core processors development has made multi-threaded software development for distributed memory applications pervasive. Unfortunately, writing correct multi-threaded programs is challengeable. Effective testing for multi-threaded programs plays an important role in the development life cycle. While coverage criteria to measure the quality of test cases for sequential programs are rich and mature, there are no adequate coverage criteria of multi-threaded programs. This project proposes a coverage criteria hierarchy for point-to-point multi-threaded programs testing, including seven (five new) coverage criteria. The property set of each criterion is formulated and the size of the coverage space for each criterion is formally mathematically examined and discussed. As for generating coverage tasks of each criterion, this project chiefly provides two main approaches, one for code coverage criteria and the other for structural coverage criterion. Regarding automatically extracting coverage tasks for code coverage criteria, we suggest querying particular nodes in the abstracted syntax tree (AST) of the program. An AST is created at the frond-end stage of compilation process. As for coverage tasks which are produced by analyzing program structure, a method to automatically construct the program model, Event InterAction Graph (EIAG), we adopted is also provided. Furthermore, methods for distinguishing legal coverage tasks are explained. Finally, we take a multi-threaded program written in XC programming language, supported by XMOS Semiconductor, as an example to evaluate the coverage criteria hierarchy.