The Find and Call app would capture users' phone book contacts and transmit them to a remote server, security company Kasperky Lab discovered.
Apple and Google removed an app from their app stores after it was revealed to be harvesting users' phone contacts as spam targets.
The Find and Call app was originally thought to be an SMS worm but later discovered to be a Trojan, according to Kaspersky Lab. The Russian software security firm said it alerted by Apple and Google to the presence of the malware in their stores, leading to the app's removal.
Apple confirmed it removed the app for violating App Store rules.
"The Find & Call app has been removed from the App Store due to its unauthorized use of users' Address Book data, a violation of App Store guidelines," Apple spokesperson Trudy Muller told CNET.
CNET has also contacted Google for comment and will update this report when we learn more.
The app required users to register their e-mail address and phone number and then would offer to find friends from users' phone book. The phone book data would then be captured and transmitted to a remote server, Kaspersky said.
The malware would then spam the user's contacts with text messages that appeared to come from the original user and including links to download the malware.
"The 'from' field contains the user's cellphone number," the report says. "In other words, people will receive an SMS spam message from a trusted source."
Both the iOS and Android versions also uploaded users' GPS coordinates to the remote server. The app also allowed users to enter information for social networks, e-mail, and even PayPal.
The app's author told Russian blog AppleInsider.ru that the app was still in beta and blamed a "failure of one of the components" for the spam. "This bug is in process of fixing," the app author said in a translated e-mail.
While malware is no stranger to Google's app store, Kaspersky points out that this is a first for Apple.
"It is worth mentioning that there have not been any incidents of malware inside the iOS Apple App Store since its launch 5 years ago," Kaspersky Lab said.
The malware discovery comes as Apple grapples with a binary corruption problem that led to incomplete app downloads and app crashes. After reports of the problem surfaced, Apple acknowledged the issue and said was working on a solution.
Updated at 6:30 p.m. PT with Apple comment.