In the near future, billions of entities will be connected to each other through the Internet. The current trend is that an increasingly number of entities, from smart personal devices to legacy databases, are controlled by software agents. Such agents often also posses a large amount of information about both the entity and its owner. Thus, a likely scenario is that the Internet will be populated by millions of information agents, all potentially able to communicate with each other. Unfortunately, we cannot assume that these agents are benevolent and are willing to cooperate in an altruistic fashion. As the amount of money transferred via the Internet is rapidly increasing caused by the breakthrough of e-commerce, we should actually expect a similar increase in the number of malicious agents. Another aspect that contributes to the complexity of agent interaction on the Internet is a desired openness, making it difficult to engineer agent societies in a top-down manner. Rather, we will here investigate the prerequisites necessary to form stable and trustworthy societies of information agents, and discuss some open problems and methodologies for studying them. The general conclusion is that more research is needed that takes into account the presence of malicious agents.