Abstract: Interclass integration testing of object-oriented software is particularly hard. Method/message path (MM path) is defined as an interleaved sequence of method executions linked by messages. It presents well the interactions between the methods of object-oriented software, and hence fits for object-oriented integration testing. In this paper, a call-graph-based approach to generate interclass MM paths automatically is proposed. This approach is evaluated by two typical call graph construction algorithms, class hierarchy analysis and Anderson’s points-to analysis, on twelve benchmark programs. The result shows that our approach is practicable, and based on Anderson’s points-to analysis, 13.11% more interclass MM paths can be generated with 27.78% less time consumption than based on the class hierarchy analysis. Moreover, the structural coverage is increased by 2% and 7% with the MM-path-oriented test suites which are generated based on Anderson’s points-to analysis than based on the class hierarchy analysis. Therefore, Anderson’s points-to analysis outperforms the class hierarchy analysis for call-graph-based interclass MM path generation.