Clemens Sauerwein
email: clemens.sauerwein@uibk.ac.at

Christian Sillaber

Michael M Huber

Andrea Mussmann

Ruth Breu

The Tweet Advantage: An Empirical Analysis of 0-Day Vulnerability Information Shared on Twitter

Keywords: Information Security, Shared Cyber Security Information, Social Networks, Data Mining, Twitter, Security Incidents

In the last couple of years, the number of software vulnerabilities and corresponding incidents increased significantly. In order to stay up-to-date about these new emerging threats, organizations have demonstrated an increased willingness to exchange information and knowledge about vulnerabilities, threats, incidents and countermeasures. Apart from dedicated sharing platforms or databases, information on vulnerabilities is frequently shared on Twitter and other social media platforms. So far, little is known about the obtainable time advantage of vulnerability information shared on social media platforms. To close this gap, we identified 709,880 relevant Tweets and subsequently analyzed them. We found that information with high relevance for affected organizations is shared on Twitter often long before any official announcement or patch has been made available by vendors. Twitter is used as a crowdsourcing platform by security experts aggregating vulnerability information and referencing a multitude of public available webpages in their Tweets. Vulnerability information shared on Twitter can improve organizations reaction to newly discovered vulnerabilities and therefore help mitigating threats.

Introduction

In recent years, cyber attacks have increased significantly in number and have become more sophisticated while the time frame for organizations to react shrinks constantly [START_REF] Jang-Jaccard | A survey of emerging threats in cybersecurity[END_REF]. To counteract new threats, organizations are implementing vulnerability management processes, increase the internal dissemination of security information and conduct awareness trainings as an integral part of their security management process [START_REF] Soomro | Information security management needs more holistic approach: A literature review[END_REF].

The time it takes to develop, distribute and implement a patch that adequately fixes a vulnerability creates a window of exposure that organizations seek to minimize [START_REF] Arbaugh | Windows of vulnerability: A case study analysis[END_REF][START_REF] Frei | Large-scale vulnerability analysis[END_REF]. Organizations need to be able to quickly react on newly occurring threats. In doing so, they need up-to-date information about vulnerabilities, exploits, incidents, and available countermeasures [START_REF] Mell | Creating a patch and vulnerability management program[END_REF]. Threat Intelligence Sharing Platforms or vulnerability databases which keep track of security related issues for different software applications are potential information sources supporting these activities [START_REF] Sauerwein | Threat intelligence sharing platforms: An exploratory study of software vendors and research perspectives[END_REF]. For example, the National Vulnerability Database1 holds more than 104,140 Common Vulnerability Exposures (CVEs), which are standardized descriptions for publicly known information security vulnerabilities and exposures [20].

Vulnerability information is also discussed and shared on social media platforms and related informal channels [START_REF] Sauerwein | Shadow cyber threat intelligence and its use in information security and risk management processes[END_REF]. Moreover, there are grounds for the assumption that vulnerabilities may be discussed on Twitter before public disclosure [START_REF] Syed | What it takes to get retweeted: An analysis of software vulnerability messages[END_REF]. However, research and practice lacks an empirical analysis of this assumption. The research at hand addresses this gap by extracting Tweets containing vulnerability information and analyzes if there is a time advantage of obtaining vulnerability information from Twitter compared to conventional sources. Moreover, this contribution extends previous research (cf. [START_REF] Syed | What it takes to get retweeted: An analysis of software vulnerability messages[END_REF]) by analyzing the contents of referenced webpages in Tweets regarding vulnerabilities.

Our data collection is based on CVEs which are standardized security vulnerability identifiers [20]. In total, we collected a set of 709,880 Tweets between May 23, 2016 andMarch 27, 2018. Based on this dataset, the paper provides a comprehensive analysis of the collected information. We analyze how the collected vulnerability information maps to the different phases of the vulnerability lifecycle [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF]. We also assess whether vulnerabilities are discussed on Twitter before the vulnerabilities official public disclosure. Moreover, we briefly examine what types of vulnerability information (e.g. descriptions of vulnerabilities, demonstrations of exploits,...) are referenced on Twitter.

The remainder of this work is structured as follows. Section 2 discusses related work regarding information security research based on Twitter data, and background information regarding the vulnerability lifecycle and assignment of CVE identifiers. Section 3 describes our research methodology, including data collection, processing and analysis. Section 4 provides an analysis of the collected Tweets. Section 5 discusses the results and limitations of the research at hand. Finally, Section 6 concludes the paper and provides outlook on future research.

Related Work and Background Information

In this section we discuss related work, and provide background information regarding the vulnerability lifecycle model and assignment of CVE identifiers.

Related Work

Analysis of data obtained from Twitter has been used successfully in a wide variety of different research applications, ranging from earthquake detection [9] and epidemiology [START_REF] Stilo | Predicting flu epidemics using twitter and historical data[END_REF], to stock market analysis [START_REF] Bollen | Twitter mood as a stock market predictor[END_REF] or identification of cyberbullying [START_REF] Al-Garadi | Cybercrime detection in online communications: The experimental case of cyberbullying detection in the twitter network[END_REF].

Since 8% of all hyperlinks shared on Twitter are phishing or spam [START_REF] Grier | @ spam: the underground on 140 characters or less[END_REF], one field of research in the context of Twitter focuses on spam abuse detection and prevention: Spam detection research on Twitter ranges from general [START_REF] Benevenuto | Collaboration, electronic messaging, anti-abuse and spam conference[END_REF][START_REF] Wang | Don't follow me: Spam detection in twitter[END_REF] to political spam abuse detection [START_REF] Chen | Statistical features-based real-time detection of drifted twitter spam[END_REF][START_REF] Murugan | Detecting streaming of twitter spam using hybrid method[END_REF]. Moreover, the detection of accounts abused for spam [START_REF] Lee | WarningBird: A near real-time detection system for suspicious URLs in twitter stream[END_REF][START_REF] Shen | Detecting spammers on twitter based on content and social interaction[END_REF], and spamming strategies [START_REF] Chen | Spammers are becoming "smarter" on twitter[END_REF] have been intensively analyzed.

Other works in the field focus on the detection of security information shared on Twitter. For example, Erkal et al. applied machine learning to Twitter data to distinguish between cyber security and non-cyber security related Tweets [START_REF] Erkal | A new cyber security alert system for twitter[END_REF]. Several authors introduced approaches that can automatically detect cyber security events on Twitter [START_REF] Cui | Who shall we follow in twitter for cyber vulnerability?[END_REF][START_REF] Khandpur | Crowdsourcing cybersecurity[END_REF][START_REF] Ritter | Weakly supervised extraction of computer security events from twitter[END_REF][START_REF] Sceller | SONAR[END_REF][START_REF] Trabelsi | Mining social networks for software vulnerabilities monitoring[END_REF]. Sabottke et al. [START_REF] Sabottke | Vulnerability disclosure in the age of social media: exploiting twitter for predicting real-world exploits[END_REF] introduced an approach to predict exploits based on Twitter discussions. Syed [START_REF] Syed | Analyzing software vendors patch release behavior in the age of social media[END_REF] analyzes the impact of social media posts on the patching behavior of vendors.

Apart from spam abuse and security information detection, Twitter was used as an information source for empirical investigations in the field of information security. For example, Jeske et al. [START_REF] Jeske | Security information sharing via twitter:'heartbleed'as a case study[END_REF] examined the extent to which specific communities of Twitter users were engaged in the debate about the Heartbleed security bug. Moreover, Syed et al. [START_REF] Syed | What it takes to get retweeted: An analysis of software vulnerability messages[END_REF] conducted an empirical study to identify the major content categories contained in vulnerability discussions on Twitter and what factors impact the Re-tweeting of these contents. Moreover, Bilge and Dumitras [START_REF] Bilge | Before we knew it: an empirical study of zero-day attacks in the real world[END_REF] empirically analyze data from real hosts to identify attacks before and after public disclosure.

Our contribution extends the discussed related work, especially [START_REF] Syed | What it takes to get retweeted: An analysis of software vulnerability messages[END_REF], through an empirical analysis of the obtainable time advantage from vulnerability information shared on Twitter. In doing so, we analyze the available information with respect to the different phases of the vulnerability lifecycle [START_REF] Arbaugh | Windows of vulnerability: A case study analysis[END_REF][START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF] and the types of referenced information. To the best of our knowledge, no prior empirical research has been conducted to analyze the time behavior of vulnerability related Tweets on Twitter.

Vulnerability Lifecycle

As depicted in Figure 1, the lifecycle of a vulnerability [START_REF] Arbaugh | Windows of vulnerability: A case study analysis[END_REF] can be divided into three phases: The (1) black risk phase, (2) gray risk phase, and (3) white risk phase. A vulnerability is in the (1) black risk phase from the time of its discovery to the time of its validated public disclosure to a wider audience. In this context, it is worth mentioning that the discovery of a new vulnerability is not publicly known until public disclosure. Since it is not feasible to read all security related information sources (e.g., mailing lists) or underground information sources (e.g., Darknet) to identify new vulnerabilities we follow Frei et al. [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF] who define the time of public disclosure "[...] as the first date a vulnerability is described on an information channel where the disclosed information on the vulnerability is (a) freely available to the public, (b) published by a trusted and independent channel and (c) has undergone analysis by experts such that risk rating information is included " [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF]. Accordingly we assume that the public disclosure of a vulnerability is the publication of a vulnerability on the National Vulnerability Database2 .

The black risk phase is followed by the (2) gray risk phase. The gray risk phase begins with the public disclosure or 0-day of the vulnerability and ends with the availability of a vendor approved countermeasure (e.g., patch). Frei et al. describe this timespan as the window of exposure. Risk exposure in this phase is especially high as the public is aware of a vulnerability without official countermeasures being available [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF].

The (3) white risk phase completes the lifecycle. It starts with the release of a vendor approved countermeasure (e.g., patch etc.) and concludes with its roll out on the vulnerable system. Unfortunately, in most of the cases, the availability of official countermeasures lags behind the public disclosure of a vulnerability [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF].

As depicted in Figure 1, an exploit might become available in any phase. According to [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF], the point in time during the vulnerability life cycle when an exploit appears has immense impact on the risk for the affected system. For example, as depicted in Figure 1, if an exploit appears during the black risk phase, nobody is yet aware of the vulnerability, though it can be exploited.

Assignment of CVE Identifiers

The assignment of CVE identifiers takes place before official public disclosure (during the black risk phase) of a vulnerability on the National Vulnerability Database [20]. CVE identifiers enable researchers and vendors to assign IDs to new vulnerabilities and facilitate the tracking of vulnerabilities over time on different information channels [20]. The general workflow of assigning CVE identifiers is the following: First, a researcher or vendor detects a new vulnerability. Second, she requests a CVE identifier from a CVE Numbering Authority which assigns it to the detected vulnerability. From this moment on, the vulnerability appears as a candidate on the MITRE webpage 3 and all discussion regarding this vulnerability should contain the assigned CVE identifier. In the meantime security experts from the MITRE or National Vulnerability Database analyze and validate the vulnerability to become an official approved CVE entry. Thereby, the security experts decide if it is a vulnerability or not. For example, they eliminate false positives or duplicates. If it is a validated CVE entry, it will be published on the National Vulnerability Database and MITRE marks it as validated. This point in time can be described as the public disclosure of a vulnerability on a trusted, independent and publicly available channel (cf. [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF]).

Research Methodology

In order to facilitate the efficient collection of Tweets distributed over different accounts, we collected data using a keyword search through the Twitter Streaming Application Programming Interface (API). We searched for Tweets matching the aforementioned CVE identifiers. CVE identifiers are unique and correspond to the following pattern: CVE-\d{4}-\d{4}\d* [20] (e.g., a valid CVE identifier might be CVE-2016-5696). In doing so, we ensured that we only obtain Tweets containing vulnerability related information. To eliminate Tweets containing wrong or untrustworthy information, we cross-validated CVE identifiers included in the obtained Tweets against CVE identifiers listed on the MITREs webpage (assigned CVEs) and National Vulnerability Database (expert validated CVEs). Tweets without any matches were excluded from further processing.

We enriched the obtained Tweets with additional information from the National Vulnerability Database containing more than 104,140 (Accessed: May 30th, 2018) validated CVE entries with corresponding descriptions. The resulting dataset for statistical analysis contained the following information about every collected Tweet: Release date, content of the Tweet, user name, referenced websites, retweet status, and further information about the considered vulnerability including the date of public disclosure, description of vulnerability, and associated CVE identifiers. We converted all timestamps (e.g., release dates) to Central European Time Zone (CET). Moreover, if available, we enriched the collected Tweets with information about known exploits obtained from the Exploit Database4 , including descriptions and release dates of exploits for certain vulnerabilities. In order to identify and label Tweets created by bots, we used the BotOrNot API [START_REF] Davis | Botornot: A system to evaluate social bots[END_REF] which implements a supervised learning method for identifying social bots. We selected the BotOrNot API due to the high accuracy it has shown in previous research [START_REF] Suárez-Serrato | On the influence of social bots in online protests[END_REF].

We used R-project 5 to statistically analyze the collected and processed data. In doing so, we mapped the collected Tweets to the vulnerability lifecycle model of each identified CVE and calculated the timespan between the occurrence of the first Tweet regarding a CVE and its public disclosure on the National Vulnerability Database. Secondly, we analyzed the referenced websites in the Tweets and manually classified them according to the four types defined in Section 4.3. In doing so, two of the authors of this publication independently classified the 500 most frequently referenced websites. Finally, the two classification results were compared. If discrepancies were identified they were resolved through discussion and reclassification by the two authors.

Results

The following section outlines the results of our data analysis and discusses them. At first, we describe some general observations made about the collected Tweets. Secondly, we map the collected Tweets to the vulnerability lifecycle model [START_REF] Arbaugh | Windows of vulnerability: A case study analysis[END_REF]. Finally, we briefly analyze and discuss the contents of the collected Tweets.

General Observations

The described data collection method delivered a set of 709,880 Tweets, containing 24,267 distinct CVE identifiers over a period of one year, ten months and five days, starting on May 23, 2016 and ending on March 27, 2018.

The raw dataset contains 205,255 Re-tweets6 , which accounts for 28.9% of the collected Tweets. On average, 1,077 Tweets appeared per day, where the minimum was 24 and the maximum was 5,531 Tweets per day. Moreover, per CVE on average 29 Tweets appeared with a minimum of one tweet per CVE and a maximum of 10,700 Tweets per CVE. The obtained Tweets were generated by 58,644 different user accounts.

While the average number of Tweets per user is 12.1 Tweets, the maximum amount of Tweets for a user in our data set is 36,890. Moreover, 70% of the Tweets in our dataset were generated by 100 accounts, 92% of which are bots. In total, 82% of the Tweets were generated by bots and 8% by human users. The remaining 10% could not be classified by the BotOrNot API. An analysis of the top 100 user time zones showed that users from the United States of America and Europe dominated our dataset, accounting for roughly 90% of all Tweets.

Mapping the Collected Tweets to the Vulnerability Lifecycle

In order to analyze if there is a time advantage of obtaining vulnerability information from Twitter compared to conventional sources (i.e. official Vulnerability databases), we mapped the collected Tweets to the vulnerability lifecycle model [START_REF] Arbaugh | Windows of vulnerability: A case study analysis[END_REF] (as described in Section 2). We created a timeline for every CVE identifier containing all Tweets referencing it, its public disclosure date, and (if available) the release date of the first exploit. As discussed in Section 3.1, we assume the publication of a vulnerability on the National Vulnerability Database as the point of public disclosure. As mentioned in Section 3, it is worth mentioning that a differentiation between gray and white risk phase was out of scope for this study as we did not include information on countermeasures.

In order to better understand how information is shared on Twitter during black risk and gray or white risk phases, we define and distinguish between the following three patterns: (1) Tweet-Disclosure-Pattern: The first tweet referencing a vulnerability appears before its public disclosure during the black risk phase. (2) Disclosure-Tweet-Pattern: The first tweet referencing a vulnerability appears after its public disclosure during the gray/white risk phase. (3) Tweet-Pattern: A tweet referencing a vulnerability appears but public disclosure did not take place during our observation.

Our investigations covered 24,267 different vulnerabilities in total. Our analysis identified the Disclosure-Tweet-Pattern for 69.6% [START_REF] Jang-Jaccard | A survey of emerging threats in cybersecurity[END_REF]879), the Tweet-Disclosure-Pattern for 25.7% (6,232) and the Tweet-Pattern for 4.7% (1,156) of the vulnerabilities. This result shows that the majority of vulnerabilities receive increased attention during the gray/white risk phase of the vulnerability lifecycle, while approximately one quarter of the vulnerabilities is discussed on Twitter during the black risk phase.

The Tweet-Disclosure-Pattern is interesting for organizations and security experts as information about vulnerabilities is shared before the public disclosure of the vulnerability to a wider audience. Consequently, there might be a time advantage of obtaining vulnerability information from Twitter compared to conventional sources, such as the National Vulnerability Database.

In order to get a better understanding we want to take a closer look on CVE-2016-5696, where the Tweet-Disclosure-Pattern can be observed. CVE-2016-5696 describes a vulnerability in the Linux kernel that allows the hijacking of TCP connections in a fast and reliable way [START_REF] Cao | Off-path tcp exploits: Global rate limit considered dangerous[END_REF]. The vulnerability was officially published on the National Vulnerability Database on August 6, 2016, which marks the day of public disclosure. A corresponding patch for the Red Hat enterprise Linux Kernel was released 7 on August 18, 2016 which marks the beginning of the white risk phase. Figure 2 shows the number of Tweets collected per day over time referencing the CVE-2016-5696 vulnerability. The timeline depicts a 45 day period beginning with the first occurrence of a relevant tweet on the July 12, 2016 and ending on August 25, 2016 8 . The public disclosure and patch release dates are marked in Figure 2. Accordingly, the timeline can be divided into the three phases of the vulnerability lifecycle, which are shown on the Xaxis. During the black risk phase, 14 Tweets were collected, the first of which was tweeted on July 12, 2016. These Tweets contained information regarding the vulnerability by referencing blogs of security experts discussing them. As mentioned above and depicted in Figure 2, the gray risk phase was initialized by the public disclosure of the vulnerability on August 6 ,2016 to a wider audience by the National Vulnerability Database. It is significant that the amount of daily Tweets increased immediately after public disclosure. In total, 741 Tweets were collected during the gray risk phase. These Tweets contained demonstration videos on how to exploit the vulnerability, descriptions of countermeasures, and discussions regarding the vulnerability. On August 18, 2016 the patch for CVE-2016-5696 was released, which concluded the gray risk phase and started the white risk phase. During this phase, we observed many Tweets about the patch and its availability.

The most interesting observation about the aforementioned Tweet-Disclosure-Pattern is that there are Tweets available discussing the vulnerability during the black risk phase -i.e. before public disclosure. Our investigations showed that minimal one, maximal 972 and on average 9.66 Tweets per CVE appeared on Twitter before the public disclosure of a vulnerability. Moreover, we observed that the first Tweet of a vulnerability covering the Tweet-Disclosure-Pattern appears on average 33.10 days before public disclosure.

Figure 3 shows the frequency distribution of Tweets regarding vulnerabilities following the Tweet-Disclosure-Pattern. The Y-axis describes the number of Tweets and the X-axis the timeline, where 0 marks the time of public disclosure. For example, a tweet appearing at a point marked with -10 means that it was tweeted ten days before public disclosure. Moreover, the red bars show the total number of Tweets excluding Re-tweets and the blue bars show the number of Re-tweets. As depicted in Figure 3, an information peak can be identified in proximity to the public disclosure (point in time = 0) where in total 5,182 Tweets appeared. Moreover, a second peak can be observed six days before public disclosure. A closer look on the Tweets appearing on this day showed that high profile vulnerabilities gained increased attention. For example, CVE-2017-0144 9 which is used by the Wannacry Ransomware [START_REF] Mohurle | A brief study of wannacry threat: Ransomware attack 2017[END_REF] was discussed intensively. Figure 3 shows that there is an increased attention during the black risk phase, starting six to seven days before public disclosure, increasing until public disclosure and rapidly decreasing after it. Moreover, the retweet rate is higher before public disclosure compared to the time afterwards.

A comprehensive analysis of the whole dataset, including all three (Tweet, Tweet-Disclosure, Disclosure-Tweet) patterns showed that the first tweet of a vulnerability appears on average 4. average per vulnerability, 2.7 Tweets appear before and 18.68 Tweets after its public disclosure.

Contents of the Collected Tweets

The analysis of the contents of the collected Tweets showed that in 80% (567,904 Tweets) of the cases, security experts and bots tend to reference external websites in their posts. This might be traced back to a lack of space in Twitter posts. Previous research [START_REF] Syed | What it takes to get retweeted: An analysis of software vulnerability messages[END_REF] has analyzed the contents of Tweets discussing vulnerability information on Twitter without considering the referenced websites. We extend it through analyzing the contents of the referenced websites with respect to the vulnerability lifecycle model. Our analysis of the 500 most referenced websites showed that they primarily contain the following four types of information:

1. Descriptions of vulnerabilities: Researchers, vendors, security experts as well as bots often reference websites describing emerging vulnerabilities in more detail. For example, we identified Tweets referencing security mailing lists, expert blogs or vulnerability databases. Moreover, we found that this type of information is quite frequent, accounting for 90% of all Tweets during black risk phase. 2. Demonstrations of exploits: Twitter users inform the Twitter community of the existence of an exploit for a certain vulnerability by referencing videos or blog entries demonstrating the exploit. For example, our data dump contains 1,603 Youtube videos describing how to exploit various vulnerabilities. We observed that this type of information can be identified on Twitter throughout all phases of the vulnerability lifecycle.

Unofficial proposals of countermeasures: Normal Twitter users frequently

propose links to unofficial work arounds and countermeasures in order to mitigate the severity of a vulnerability prior to official patch release. For example, we identified Tweets discussing and referencing security blogs describing unapproved countermeasures. This type of information primarily can be found during gray risk phase and is of potential value since an official countermeasure is not available. 4. Announcements of patch releases: Vendors inform the community about official available countermeasures (e.g., patches) by referencing their webpages for further information regarding it. It is not surprising that this type of information appears on Twitter in close proximity to the time an official patch is released.

The identified four types of information are distributed as follows: 59.3% Descriptions of vulnerabilities, 12.2% Announcements of patch release, 13.5% Unofficial proposals of countermeasures, 6.7% Demonstrations of exploits. The remaining 8.3% were not classifiable.

Discussion and Limitations

In the following Section, we discuss the results and their implications for research and conclude this Section with a discussion of the limitations of the research at hand.

Discussion of Results

The main goal of our investigations was to analyze the nature, timeliness and types of vulnerability information shared on Twitter in order to show how organizations can benefit. Vulnerability information shared on Twitter should be treated with care as it originates from not validated sources. In order to counteract this limitation, we based our data collection on CVE identifiers (see Section 3.2) and cross-validated the collected Tweets with information obtained from the National Vulnerability Database. In doing so, we ensured that we collected information covering information security topics, like discussions on vulnerabilities, threats or countermeasures. The subsequent mapping of the collected Tweets to the vulnerability lifecycle model [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF] showed that the majority of vulnerabilities are discussed on Twitter at the same time as their public disclosure or shortly afterwards. Moreover, we identified a peak of Tweets in close proximity to the vulnerabilitys public disclosure, which can be traced back to a high number of Re-tweets and tweeting bots (see Figure 3). This is a clear indicator that the information security community tends to discuss and exchange security information during public disclosure more actively.

We found that nearly one quarter of the Tweets follow the Tweet-Disclosure-Pattern which means that Tweets discussing certain vulnerabilities appear before their public disclosure or before the availability of countermeasures. According to this observation, security information shared on Twitter can be more current than conventional, validated information sources, such as vulnerability databases and can serve as potential real-time sensor on insider knowledge about emerging topics in information security. Due to this fact, we empirically confirm the assumption of [START_REF] Syed | What it takes to get retweeted: An analysis of software vulnerability messages[END_REF] that vulnerability information appears on Twitter before public disclosure. Consequently, we see a time advantage for security experts to stay informed about emerging vulnerabilities.

As discussed in Section 4.3, 80% of the collected Tweets contain references to websites containing information regarding vulnerabilities, exploits, unofficial countermeasures and official patch releases. According to this observation it can be stated that Twitter serves as crowdsourcing platform were security experts and bots aggregate vulnerability information by referencing a multitude of public available webpages in their Tweets. Consequently, vulnerability information shared on Twitter can be used by organizations to find valuable public available information sources to timely react on newly discovered vulnerabilities and mitigate emerging threats.

A closer look on the different types of referenced information sources (see Section 4.3) showed that links to demonstrations of exploits are the most interesting ones. We identified several cases where information on how to exploit a certain vulnerability was posted on Twitter during the black or gray risk phase. For example, we found Tweets referencing Youtube videos demonstrating a certain exploit during black risk phase. According to [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF], the point in time during the vulnerability lifecycle where an exploit appears has immense impact on the risk a system affected by certain vulnerabilities is exposed to. A tweet demonstrating an exploit of a vulnerability during the black risk phase is serious since affected organizations might not be aware of the vulnerability and an incident might go unnoticed. In addition, an exploit appearing during gray risk phase might be serious as well, as countermeasures might be not yet available. Moreover, exploit information shared on Twitter before a countermeasure is available are also a serious threat for affected organizations as attackers might use the knowledge to exploit a certain vulnerability. However, exploit information shared on Twitter might be beneficial for organizations as they might be able to stay informed about potential threats and might put suitable countermeasures in place early.

Moreover, our analysis showed that nearly 82% of the Tweets were generated by bots tweeting a reference to a website discussing a specific vulnerability. An analysis of the remaining 18% generated by humans showed a similar pattern. As 80% of all Tweets follow this pattern and the referenced websites by humans and bots appear during all phases of the vulnerability lifecycle and provide valuable information a difference between the human or bot generated contents can not be observed.

Limitations

Limitations that have to be acknowledged and accounted for regarding our research are: (1) selection bias of relevant Tweets, (2) Twitters data access limit, (3) vague definition of public disclosure, and (4) researchers biasing the analysis of websites through classification mistakes.

In order to counteract (1), we collected all Tweets that contained a valid CVE identifier and cross-validated them with the CVEs contained in the National Vulnerability Database. Tweets that do not contain a CVE identifier were not collected. It is worth mentioning that we primarily focus on CVE-based Tweets which exclude all cyber security-related Tweets that do not reference a respective CVE identifier. There might be the possibility of type (2) limitations, since Twitter limits the public streaming API to only one percent of the daily total number of new Tweets. As the number of daily collected Tweets was below this limit, we were able to crawl all Tweets which were relevant. overcome (3), we decided to rely on the original definition of public disclosure by [START_REF] Frei | 0-day patch-exposing vendors(in) security performance[END_REF]. Therefore, we considered the official release data of CVEs on the National Vulnerability Database as public disclosure of a vulnerability to a wider audience. There might be the possibility that researchers made classification mistakes during analysis (cf (4)). We manually classified the 500 most referenced websites. As described in Section 3 two researchers independently classified the websites and the results were compared. If classification discrepancies were discovered they were limited through reclassification.

Conclusion and Future Work

In this paper, we present an empirical analysis of the obtainable time advantage of vulnerability information shared on Twitter. We collected 709,880 Tweets between May 23, 2016 andMarch 27, 2018 and mapped the obtained Tweets to the vulnerability lifecycle model. We observed that one quarter of the examined vulnerabilities were discussed on Twitter before public disclosure by official entities or vendors. Consequently, Twitter can provide a time advantage to react on newly discovered vulnerabilities. Moreover, we observed that Twitter serves as a security crowdsourcing platform for security information which reaches a considerable number of users and organizations. Our analysis identified the following types of information which are referenced in the collected Tweets: (1) Description of vulnerabilities, (2) Demonstrations of exploits, (3) Unofficial proposals of countermeasures, (4) Announcements of patch releases. Future work will focus on social graph analysis of the obtained information in order to identify patterns of collaboration and the development of a prediction model for the severity of vulnerabilities based on the Twitter history of the Tweets authors.

7

  https://rhn.redhat.com/errata/RHSA-2016-1633.html (Accessed: May 30th, 2018) 8 Note: Due to space limitations, we did not show the full white risk phase.

Fig. 2 .

 2 Fig. 2. The vulnerability lifecycle of CVE-2016-5696

Fig. 3 .

 3 Fig. 3. Frequency distribution of 100 most mentioned vulnerabilities following the Tweet-Disclosure-Pattern.

Time Discovery of Vulnerability Disclosure of Vulnerability Countermeasure Available Countermeasure Implemented Black Risk Grey Risk White Risk Exploit

	Fig. 1. Vulnerability lifecycle (based on [2, 14])

https://nvd.nist.gov/ (Accessed: May 30th,

2018) 0-Day Vulnerability Information Shared on Twitter

https://nvd.nist.gov/ (Accessed: May

30th, 2018) 3 https://cve.mitre.org/cve/ (Accessed: May 30th, 2018)

https://www.exploit-db.com/ (Accessed: May 30th, 2018)

https://www.r-project.org/ (Accessed: May 30th, 2018)

A retweet is a repost of a message posted by an user.


Dusko Pavlovic

Muzamil Yahia
email: muzamil@hawaii.edu

Monoidal computer III: A coalgebraic view of computability and complexity ⋆ (Extended abstract)

Monoidal computer is a categorical model of intensional computation, where many different programs correspond to the same inputoutput behavior. The upshot of yet another model of computation is that a categorical formalism should provide a high-level language for theory of computation, flexible enough to allow abstracting away the low level implementation details when they are irrelevant, or taking them into account when they are genuinely needed. A salient feature of the approach through monoidal categories is the formal graphical language of string diagrams, which supports geometric reasoning about programs and computations. In the present paper, we provide a coalgebraic characterization of monoidal computer. It turns out that the availability of interpreters and specializers, that make a monoidal category into a monoidal computer, is equivalent with the existence of a universal state space, that carries a weakly final state machine for all types of input and output. Being able to program state machines in monoidal computers allows us to represent Turing machines, and capture the time and space needed for their executions. The coalgebraic view of monoidal computer thus provides a convenient diagrammatic language for studying not only computability, but also complexity.

Introduction

In theory of computation, an extensional model reduces computations to their set theoretic extensions, computable functions, whereas an intensional model also takes into account the multiple programs that describe each computable function [START_REF] Barendregt | The lambda calculus: its syntax and semantics[END_REF][START_REF] Odifreddi | Classical Recursion Theory : The Theory of Functions and Sets of Natural Numbers[END_REF]II.3].

In computer science, this semantical gamut got refined on the extensional side by denotational models, that take into account not just computable functions but also some computational effects, and on the intensional side by operational models, where the meaning of a program is specified up to an operational equivalence [START_REF] Bruni | Models of Computation[END_REF][START_REF] Winskel | The Formal Semantics of Programming Languages: An Introduction[END_REF]. Categorical semantics of computation arose from the realization that ⋆ Partially supported by AFOSR and NSF.

cartesian closed categories provide a simple and effective framework for studying the extensional models [START_REF] Lambek | Introduction to Higher Order Categorical Logic[END_REF]. Both denotational and operational semantics naturally developed as extensions of this categorical framework [START_REF] Moggi | Notions of computation and monads[END_REF][START_REF] Turi | Towards a mathematical operational semantics[END_REF].

The goal of the monoidal computer project is to provide categorical semantics of intensional computation. This turns out to be surprisingly simple technically, but subtle conceptually. In this section, we describe the structure of monoidal computer informally, and try to explain it in the context of categorical semantics. In the rest of the paper, we spell out some of its features formally, in particular the coalgebraic part.

Categorical computability: context and concept

The step from a cartesian closed category C, as an extensional model of computation, to a monoidal computer C, as an intensional model, can be summarized as follows:

C (X, [A, B]) C(X × A, B) ε AB X ∼ = λ AB X C • (X, P) C(X ⊗ A, B) γ AB X (1)
The first line says that a category C is cartesian closed when it has the (cartesian) products X × A and a family of bijections, natural in X and indexed over the types A and B, between the morphisms X × A -→ B and X -→ [A, B].

If a morphism X × A f -→ B is thought of as an X-indexed family of computations with the inputs from A and the outputs in B, then the corresponding morphism X λ AB X (f ) -----→ [A, B] can be thought of as the X-indexed family of programs for these computations. This structure is the categorical version of the simply typed extensional lambda calculus: λ AB X corresponds to the operation of abstraction, whereas ε AB X corresponds to the application [24, Part I]. The equation ε AB X • λ AB X = id says that if we abstract a computation into a program, and then apply that program to some data, then we will get the same result as if we executed the original computation on the data. This is the β-rule of the lambda calculus, the crux of Alonzo Church's representation of program evaluations as function applications of λ-abstractions [START_REF] Church | An unsolvable problem of elementary number theory[END_REF]. The equation λ AB X • ε AB X = id says that if we apply a program, and then abstract out of the resulting computation a program, then we will get the same program that we started from. This is the η-rule of the lambda calculus: the extensionality. Dropping the second equation thus corresponds to modeling the non-extensional typed lambda calculus, with weak exponent types. While this structure was sometimes interpreted as a model of intensional computation, and interesting results were obtained [START_REF] Hoofman | Comparing models of the intensional typed λ-calculus[END_REF], the main result was that every such non-extensional model is essentially extensional, in the sense that it contains an extensional model as a retract [START_REF] Hayashi | Adjunction of semifunctors: Categorical structures in nonextensional lambda calculus[END_REF]. In genuinely intensional models, identifying extensionally equivalent programs is not computable.

The structure of a monoidal computer C is displayed in the second line of (1). There are three changes with respect to the cartesian closed structure: a) the bijections ε AB X are relaxed to surjections γ AB X ; b) the exponents [A, B] are replaced with the type P of programs, the same for all types A and B; and c) the product × is replaced with a tensor ⊗, and C is not a cartesian category, but C • on the left is its largest cartesian subcategory with ⊗ as the product. We try to clarify these changes in the next three paragraphs.

Change (a) means that we have not only dropped the extensionality equation λ AB X • ε AB X = id, but eliminated the abstraction operation λ AB X altogether. All that is left of the bijection between the abstractions and the applications, displayed in the first line of (1), is a surjection from programs to computations, displayed in the second line of (1): for every X-indexed family of computations

X ⊗ A f -→ B there is an X-indexed family of programs X F -→ P such that f = γ AB X (F
(F ) = {F } AB = f .
Change (b) means that all programs are of the same type P. The central feature of intensional computation is that any program can be applied to any data, and in particular to itself. The main constructions of computability theory depend on this, as we shall see in Sec. 3.4. If computations of type A -→ B were encoded by programs of a type depending on A and B, let us write it in the form ⌈A, B⌉, then such programs could not be applied to themselves, but they could only be processed by programs typed in the form ⌈⌈A, B⌉, C⌉. That is why all programs must be of the same type P. We will see in Sec. 3.3 that this implies that all types must be retracts of P. This does not imply that the type structure of a monoidal computer can be completely derived from an applicative structure on P, as an essentially untyped model of computation [24, I.15-I.17]. The type structure of monoidal computer, can be derived from internal structure of P if and only if the model is essentially extensional (i.e., it contains an extensional retract, like before). But where does the monoidal structure come from?

Change (c) makes monoidal computers into monoidal categories, not cartesian. Just like cartesian categories, monoidal computers have the diagonals and the projections for all types, which are necessary for data copying and deleting, as explained in Sec. 2. Unlike in cartesian categories, though, the diagonals and the projections in monoidal computers are not natural. The projections are not natural because intensional computations may not terminate: they are not total morphisms. The diagonals are not natural when the computations are not deterministic: they are then not single-valued as morphisms. While intensional computations can be deterministic, and the diagonals in a monoidal computer can all be natural, if all projections are natural, i.e. if all computations are total, then the model contains an extensional retract. A monoidal computer is thus a cartesian category if and only if it is essentially extensional. That is why a genuinely intensional monoidal computer must be genuinely monoidal. On the other hand, even a computation that is nowhere defined has a program, and pro-grams are always well-defined values. So while the indexed families of intensional computations cannot all be total functions, the corresponding indexed families of programs must all be total functions. That is why the category C • on the left in (1) is different from C: it is the largest subcategory of C for which ⊗ is the cartesian product.

In summary, dropping or weakening any of the changes described in (ac) leads to the same outcome: an essentially extensional model. For a genuinely intensional model it is thus necessary to have (c) a genuinely monoidal structure, (b) untyped programs, and (a) no computable program abstraction operators. It was shown in [START_REF] Pavlovic | Monoidal computer I: Basic computability by string diagrams[END_REF][START_REF] Pavlovic | Basic Concepts of Computer Science (with Pictures)[END_REF] that this is also sufficient for a categorical reconstruction of the basic concepts of computability. Sections 2 and 3 provide a brief overview of this. But our main concern in this paper is complexity.

Categorical complexity: A coalgebraic view

To capture complexity, we must capture dynamics, i.e. access the actual process of computation. This, of course, varies from model to model, and different models of computation induce different notions of complexity. Abstract complexity [START_REF] Blum | A machine-independent theory of the complexity of recursive functions[END_REF] provides, in a sense, a model-independent common denominator, which can be viewed as an abstract notion of complexity; but the categorical view of computations as morphisms at the first sight does not even provide a foothold for abstract complexity. We attempted to mitigate the problem by extending the structure of monoidal computer by grading [START_REF] Pavlovic | Monoidal computer II: Normal complexity by string diagrams[END_REF], but the approach turned out to be impractical for our goals (indicated in the next section). Now it turns out to also be unnecessary, since dynamics of computation can be captured using the coalgebraic tools available in any monoidal computer.

Coalgebra is the categorical toolkit for studying dynamics in general [START_REF] Pavlović | Calculus in coinductive form[END_REF][START_REF] Jan | Universal coalgebra: a theory of systems[END_REF], and dynamics of computation in particular [START_REF] Klin | Bialgebras for structural operational semantics[END_REF][START_REF] Pavlovic | Testing semantics: Connecting processes and process logics[END_REF][START_REF] Turi | Towards a mathematical operational semantics[END_REF]. Coalgebras, as morphisms in the form X -→ EX for an endofuctor E, provide a categorical view of automata, state machines, and processes with state update [START_REF] Jacobs | Introduction to Coalgebra: Towards Mathematics of States and Observation[END_REF][START_REF] Pavlovic | Smooth coalgebra: testing vector analysis[END_REF]; the other way around, all coalgebras can be thought of as processes with state update. In the framework on this paper, only a very special class of coalgebras will be considered, as the morphisms in the form X×A -→ X×B, corresponding to what is usually called Mealy machines [8,14,17, . . . ]. In the presence of the exponents, such morphisms can be transposed to proper coalgebras in the form

X -→ [A, X × B].
But coalgebra provides a categorical reconstruction of state machines even without the exponents, since the homomorphisms remain the same, and the category of machines is isomorphic to a category of coalgebras even if the objects are not presented as coalgebras in the strict sense. Our "coalgebras" will thus be in the form

X × A -→ X × B, or more generally X ⊗ A -→ X ⊗ B.
The crucial step in moving the monoidal computer story into the realm of coalgebra is to replace the X-indexed functions

X × A f -→ B with X-state ma- chines X × A m -→ X × B.
While a function f mapped for each index x an input a to an output b, a machine m now maps at each state x an input a to an output b, and updates the state to x ′ . This state update provides an abstract view of dynamics. Continuous dynamics can be captured in varying the same approach [START_REF] Pavlovic | Smooth coalgebra: testing vector analysis[END_REF][START_REF] Pavlović | Calculus in coinductive form[END_REF]. This step from X-indexed functions to X-state machines is displayed in the first row of the following table. cartesian closed

[A, B] × A B X × A ε ∀f ∃!λf ×A abstractions ε ←→ λ applications [A + , B] × B [A + , B] × A X × B X × A ξ ∃! m ×B ∀m ∃! m ×A behaviors - ← ---machines intensional models: monoidal computers P ⊗ A B X ⊗ A {} ∀f ∃F ×A programs - → - → computations P ⊗ B P ⊗ A X ⊗ B X ⊗ A {| |} ∃M ⊗B ∀m ∃M ⊗A adaptive programs ⇀ ⇀ processes
The representation of functions from A to B by the elements of [A, B] lifts to the representation of machines with inputs in A and outputs in B by the induced behaviors in [A + , B], where A + is the inductive type of the nonempty sequences from A. Behaviors are thus construed as functions extended in time [START_REF] Jacobs | Introduction to Coalgebra: Towards Mathematics of States and Observation[END_REF][START_REF] Pavlovic | Basic Concepts of Computer Science (with Pictures)[END_REF][START_REF] Jan | Universal coalgebra: a theory of systems[END_REF]. In the presence of list constructors, the representation of functions using the exponents [A, B] induces the representation of machines using the final machines [A + , B]. The other way around, the final machines induce the exponents as soon as the idempotents split.

The rows of the table depict the step from static models to dynamic models. The columns depict the step from the extensional to the intensional. The lefthand column is just a different depiction of (1): the upper triangle unpacks the bijection in the first line of (1), whereas the lower triangle unpacks the surjection in the second line. The right-hand column is the step from the extensional coinduction of final state machines to the intensional coinduction as implemented in the structure of monoidal computer. The bottom row of the table is the step from the monoidal computer structure presented in terms of universal evaluators, the content of Sec. 3, to the monoidal computer structure presented in terms of universal processes, the content of Sec. 4. The fact that the two presentations are equivalent is stated in Thm. 9. This coalgebraic view of intensional computation opens an alley towards capturing dynamics of Turing machines in Sec. 5, and a direct internalization of time and space complexity measures in Sec. 6. A general approach through abstract complexity is provided in the full version of the paper. A comment about the role of coalgebra in this effort is in Sec. 7. Some proofs are in the Appendix.

Background and related work

While computability and complexity theorists seldom felt a need to learn about categories, there is a rich tradition of categorical research in computability the-ory, starting from one of the founders of category theory and his students [START_REF] Eilenberg | Recursiveness. ACM Monograph[END_REF][START_REF] Di | Dominical Categories: Recursion Theory without Elements[END_REF], through extensive categorical investigations of realizability [START_REF] Pieter | Combinatorial realizability models of type theory[END_REF][START_REF] Hyland | The effective topos[END_REF][START_REF] Jaap Van Oosten | Realizability: An Introduction to its Categorical Side[END_REF], to the recent work on Turing categories [START_REF] Cockett | Introduction to Turing categories[END_REF], and on a monoidal structure of Turing machines [START_REF] Bartha | The monoidal structure of Turing machines[END_REF]. A categorical account of time complexity was proposed in [START_REF] Cockett | Timed sets, functional complexity, and computability[END_REF], using a special structure called timed sets, introduced for the purpose. While our approach in [START_REF] Pavlovic | Monoidal computer II: Normal complexity by string diagrams[END_REF] used grading in a similar way, our current approach seems closer in spirit to [START_REF] Asperti | The intensional content of Rice's Theorem[END_REF], even if that work is neither coalgebraic nor explicitly categorical. Our effort originated from a need for a framework for reasoning about logical depth of cryptographic protocols and algorithms [START_REF] Pavlovic | Gaming security by obscurity[END_REF]. The scope of the project vastly exceeded the original cost estimates [START_REF] Pavlovic | Chasing diagrams in cryptography[END_REF], but also the original benefit expectations. The unexpectedly simple diagrammatic formalism of monoidal computer turned out to be a very convenient teaching tool in several courses. 1This extended abstract is shortened to fit the conference proceedings format. The full text is available on arxiv:1704.04882.

Preliminaries

A monoidal computer is a symmetric monoidal category with some additional structure. As a matter of convenience, and with no loss of generality, we assume that it is a strict monoidal category. Monoidal categories are presented in many textbooks, e.g. [25, Sec. VII.1 and Ch. XI].

We call data service the structure that allows passing the data around in a monoidal category. In computer programs and in mathematical formulas, the data are usually passed around using variables. They allow copying and propagating the data values where they are needed, or deleting them when they are not needed. The basic features of a variable are thus that it can be freely copied or deleted. The basic data services over a type A in a monoidal category C are the copying operation A ∆ -→ A ⊗ A, and the deleting operation A ⊤ -→ I, which together form a commutative comonoid, i.e. satisfy the equations

= = = ∆ ; (∆ ⊗ A) = ∆ ; (A ⊗ ∆) ∆ ; (⊤ ⊗ A) = ∆ ; (A ⊗ ⊤) = idA = ∆ ; σ = ∆
The correspondence between variables and comonoids was formalized and explained in [START_REF] Pavlovic | Categorical logic of names and abstraction in action calculus[END_REF]. The algebraic properties of the binary copying induce unique A,B) is a map if it is a comonoid homomorphism with respect to the data services on A and B, which means that it satisfies the following equations

n-ary copying A ∆ -→ A ⊗n , for all n ≥ 0. The tensor products ⊗ in C are the cartesian products × if and only if every A in C carries a canonical comonoid A × A ∆ ← -A ⊤ -→ 1,
= f f f = f f ; ∆B = ∆A ; (f ⊗ f ) f ; ⊤B = ⊤A
Given a symmetric monoidal category C with data services, we denote by C • the subcategory spanned by the maps with respect to its data services, i.e. by those C-morphisms that preserve copying and deleting.

Remark. If C is the category of relations, then the first equation says that f is a single-valued relation, whereas the second equation says that it is total. Hence the name. Note that the morphisms ∆ and ⊤ from the data services are maps with respect to the data service that they induce. They are thus contained in C • , and each of them forms a natural transformation with respect to the maps. This just means that the tensor ⊗, restricted to C • , is the cartesian product.

3 Monoidal computer

Evaluation and evaluators

Notation. When no confusion seems likely, we write AB instead of A ⊗ B, and C(X) instead of C(I, X). We omit the typing superscripts whenever the types are clear from the context. The following proposition says that program evaluations can be construed as a categorical view of Turing's universal computer [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF], or of Kleene's acceptable enumerations [43,29, II.5], or of interpreters and specializers from programming language theory [START_REF] Neil | Computability and Complexity: From a Programming Perspective[END_REF].

f ∈ C(A, B) there is a program F ∈ C • (P) such that f (a) = {F } AB a (b) a partial evaluator [ ] AB ∈ C • (PA, P) with {G} (AB)C (a, b) = [G] AB a BC b B f A = B {} F A P A {} B C = A {} [ ] B P C
Remark. Note that the partial evaluators [ ] are maps, i.e. total and single valued morphisms in C • , whereas the universal evaluators {} are ordinary morphisms in C. A recursion theorist will recognize the universal evaluators as Turing's universal machines [START_REF] Turing | On computable numbers, with an application to the Entscheidungsproblem[END_REF], and the partial evaluators as Gödel's primitive recursive substitution function S, enshrined in Kleene's S m n -theorem [START_REF] Stephen | On notation for ordinal numbers[END_REF]. A programmer can think of the universal evaluators as interpreters, and of the partial evaluators as specializers [START_REF] Neil | Computability and Complexity: From a Programming Perspective[END_REF]. In any case, (a) can be understood as saying that every computation can be programmed; and then (b) says that any program with several inputs can be evaluated on any of its inputs, and reduced to a program that waits for the remaining inputs:

= [ ] {} X A B B A X {} H H X A B = h h(x, a) {H} (x, a) {[H] x} a = = (2)
Together, the two conditions thus equivalently say that for every computation h ∈ C(X⊗A, B) there is an

X-indexed program Ξ ∈ C • (X, P) such that h(x, a) = {Ξx}a, namely Ξ = [H].
Branching. By extending the λ-calculus constructions as in [START_REF] Pavlovic | Monoidal computer I: Basic computability by string diagrams[END_REF], we can extract from P the convenient types of natural numbers, truth values, etc. E.g., if the truth values t and f are defined to be some programs for the two projections, then the role of the if-branching command can be played by the universal evaluator:

if(b, x, y) = {b} (x, y) =        x if b = t y if b = f = = t f if={} if={}

Examples of monoidal computer

Let S be a cartesian category and T : S -→ S a commutative monad. Then the Kleisli category S T of free algebras is monoidal, with the data services induced by the cartesian structure of S. The standard model of monoidal computer C is obtained by taking S to be the category of finite and countable sets, and T X = ⊥ + X to be the maybe monad, adjoining a fresh element to every set. The category S ⊥ is the category of partial functions, and the monoidal computer C ⊆ S ⊥ is the subcategory of computable partial functions:

|C| = A ⊆ N | ∃e ∈ N. {e}a ↓ ⇐⇒ a ∈ A C(A, B) = f : A ⇀ B | ∃e. {e} = f
The category C • is then the category of computable total functions. Assuming that the programs are encoded as natural numbers, the type of programs is P = N; but any language containing a Turing complete set of expressions would do, mutatis mutandis. The sequence {0}, {1}, {2}, . . . denotes an acceptable enumeration of computable partial functions [START_REF] Odifreddi | Classical Recursion Theory : The Theory of Functions and Sets of Natural Numbers[END_REF]II.5]. The universal evaluators can be implemented as partial recursive functions; the partial evaluators are the total recursive functions, constructed in Kleene's S m n -theorem [START_REF] Stephen | On notation for ordinal numbers[END_REF]. Other commutative monads T : S -→ S induce monoidal computers in a similar way, capturing intensional computations together with the corresponding computational effects: exceptions, nondeterminism, randomness [START_REF] Moggi | Notions of computation and monads[END_REF]. Some of the familiar computational monads need to be restricted to finite support. The distribution monad must be factored modulo computational indistinguishability. A simple quantum monoidal computer can be constructed using a relative monad for finite dimensional vector spaces [START_REF] Altenkirch | Monads need not be endofunctors[END_REF]. However, in the model where the universal evaluators are quantum Turing machines, the program evaluations cannot be surjective in the usual sense, but only in the topologically enriched sense, i.e., they are dense [START_REF] Bernstein | Quantum complexity theory[END_REF]. We do not know how to derive this model from a computational monad, albeit relative. Another interesting feature is that most computational effects induce nonstandard data services, corresponding to complementary bases, which are, of course, used in randomized, quantum, but also in nondeterministic algorithms [START_REF] Pavlovic | Quantum and classical structures in nondeterministic computation[END_REF][START_REF] Pavlovic | Geometry of abstraction in quantum computation[END_REF]. More examples are in [START_REF] Pavlovic | Monoidal computer I: Basic computability by string diagrams[END_REF], but most work is still ahead. Remark. In [START_REF] Pavlovic | Monoidal computer I: Basic computability by string diagrams[END_REF] we only considered the basic monoidal computer, where all types are powers of P. In the standard model, programs are encoded as natural numbers, and all data are tuples of natural numbers, which can be recursively encoded as natural numbers. Prop. 5 says that this must be the case in every computer. Note that there is no claim that either e B or d B is unique. Indeed, in nondegenerate monoidal computers, each type B has many different encoding pairs e B , d B . However, once such a pair is chosen, the fact that e B is total and single-valued means that it assigns a unique program code to each element of B. The fact that d B is not total means that some programs in P may not correspond to elements of B. Since Prop. 5 says that the program evaluations make every type into a retract of P, and Prop. 4 reduced the structure of monoidal computer to the evaluators for all types, it is natural to ask if the evaluators of all types can be reduced to the evaluators over the type P of programs. Can all of the structure of a monoidal computer be derived from the structure of the type P of programs? E.g., can the program evaluations be "uniformized" by always encoding the input data of all types in P, performing the evaluations to get the outputs in P, and then decoding the outputs back to the originally given types? Can the type structure and the evaluation structure of a monoidal computer be reconstructed by unfolding the structure of P, as it is the case in models of λ-calculus. Is monoidal computer yet another categorical view of a partial applicative structure? The answer to all these question is positive just in the degenerate case of an essentially extensional monoidal computer. If the type structure of monoidal computer can be faithfully encoded in P, then there is a retract of P which supports an extensional model of computation, i.e. allows assigning a unique program to each computation. If all evaluators can be derived by decoding the evaluators with the output type P, and if the decoding preserves the original evaluators on P, then all computation representable in monoidal computer must be provably total and single valued: it degenerates into a cartesian closed category derived from a C-monoid. For details see [24, I.15-I.17], and the references therein.

The Fundamental Theorem of Computability

In this section we show that every monoidal computer validates the claim of Kleene's "Second Recursion Theorem" [START_REF] Stephen | On notation for ordinal numbers[END_REF][START_REF] Yiannis | Kleene's amazing second recursion theorem[END_REF]. A Kleene fixed program Γ can now be constructed by partially evaluating G on itself, i.e. as

Γ = [G] G, because B A {} G = B A g G G B A {} = G B A G {} = [ ] [ ] Γ Γ = = = = g(Γ, a) g [G]G, a {G}(G, a) [G]G a {Γ } a
This theorem induces convenient representations of integers, arithmetic, primitive recursion, unbounded search and thus shows that monoidal computer is Turing complete [START_REF] Pavlovic | Basic Concepts of Computer Science (with Pictures)[END_REF]. In [START_REF] Pavlovic | Monoidal computer I: Basic computability by string diagrams[END_REF], this was done by using the λ-calculus constructions. Next section provides yet another proof, through Turing machines.

Coalgebraic view

So far, we formalized the programs -→ -→ computations correspondence from the left hand column of the table in the Introduction. But presenting computations in the form XA {F } --→ B only displays their interfaces, and hides the actual process of computation. To capture that, we switch to the right hand column of the table, and study the correspondence adaptive programs -→ -→ processes. A process is presented as a morphism in the form X ⊗ A -→ X ⊗ B. We interpreted the morphisms in the form X ⊗ A -→ B as X-indexed families of computations with the inputs from A and the outputs in B. The indices of type X can be thought of as the states of the world, determining which of the family of computations should be run. Interpreted along the same lines, a process X ⊗ A p -→ X ⊗ B does not only provide the output of type B, but it also updates the state in X. This is what state machines also do, and that is why the morphisms X × A m -→ X × B in cartesian categories are interpreted as machines. In a sufficiently complete cartesian category, every such machine m induces a machine homomorphism

X m --→ [A + , B], which assigns to each state x ∈ X a behavior m x ∈ [A + , B],
unfolded by the final AB-machine

[A + , B] × A ξ -→ [A + , B] × B.
The table in the Introduction displayed this. A monoidal computer, though, turns out to provide a much stronger form of representation for its morphisms in the form X ⊗A p -→ X ⊗ B: each of them induces a machine homomorphism X P -→ P. This P is a program for the process p. Note that there may be many programs for each process; but on the other hand, all programs, for all processes of all possible input types A and output types B, are represented in the same type of programs P. This makes a fundamental difference, distinguishing machines m from computational processes p, which include life [START_REF] John Von Neumann | Theory of Self-Reproducing Automata[END_REF][START_REF] Turing | The chemical basis of morphogenesis[END_REF] 2 . Every family of machines is designed in a suitable engineering language; but all computational processes can be programmed in any Turing complete language, just like all processes of life are programmed in the language of genes. That is why the morphisms X ⊗A p -→ X ⊗B are processes, and not merely machines. Their representations X P -→ P are not merely X-indexed programs, but they are adaptive programs, since they adapt to the state changes, in the sense that we now describe.

Definition 7. A morphism XA p -→ XB in a monoidal category C is an AB- process. If Y A r -→ Y B is another AB-process, then an AB-process homomor- phism is a C-morphism X f -→ Y such that (f ⊗ A) ; r = p ; (f ⊗ B).
{} AB = S ⊗ A {| |} AB -----→ S ⊗ B ⊤⊗B ----→ B
is a universal evaluator, and thus makes C into a monoidal computer. Towards proving [START_REF] Asperti | The intensional content of Rice's Theorem[END_REF], suppose that we are given a computation X ⊗ A h -→ B, and consider the process

h = X ⊗ A ∆⊗A ----→ X ⊗ X ⊗ A X⊗h ----→ X ⊗ B By Def. 8, there is then an X-adaptive program Ξ = h ∈ C • (X, S) satisfying the rightmost equation in the next diagram. X A B {| |} Ξ X A B = h X A B h h = X {} S S = X A h h Ξ S B
The middle equation holds because h is in C • , i.e. a comonoid homomorphism. Deleting the state update from the process yields [START_REF] Asperti | The intensional content of Rice's Theorem[END_REF]. The other way around, if C is a monoidal computer, with universal evaluators for all pairs of types, we claim that the weakly final AB-process is

{| |} AB = P ⊗ A {} A(PB) ------→ P ⊗ B
To prove the claim, take an arbitrary AB-process X ⊗ A p -→ X ⊗ B, and postcompose it with the partial evaluator on X, to get

p = P ⊗ X ⊗ A P⊗p ---→ P ⊗ X ⊗ B [ ] XBP ⊗B -------→ P ⊗ B
Using the Fundamental Theorem of Computability, Thm. 6, construct a Kleene's fixed point P ∈ C(P) of p. This completes the proof that {} A(BP) satisfies definition 8 of weakly final ABprocess, and that P is thus not only a type of programs, but also a universal state space.

Computability

In the remaining two sections we show how to run Turing machines in a monoidal computer, and how to measure their complexity. But a coalgebraic treatment of Turing machines as machines, in the sense discussed at the beginning of Sec. 4, would only display their behaviors, i.e. what rewrite and which move of the machine head will happen on which input, and it obliterates the configurations of the tape, where the actual computation happens. In terms of Sec. 4, a Turing machine as a model of actual computation should not be viewed as a machine, but as a process. So we call them Turing processes here. While changing well established terminology is seldom a good idea, and we may very well regret this decision, the hope is that it will be a useful reminder that we are doing something unusual: relating Turing machines with adaptive programs, coalgebraically. The presented constructions go through in an arbitrary monoidal computer, but require spelling out a suitable representation of the integers, and some arithmetic. This was done in [START_REF] Pavlovic | Monoidal computer I: Basic computability by string diagrams[END_REF], and can be done more directly; but for the sake of brevity, we work here with the category C of recursively enumerable sets and computable partial functions from Sec. 3.2. The monoidal structure and the data services are induced by the cartesian products of sets, which are, however, not categorical products any more, since the singleton set, providing the tensor unit, is not a terminal object for partial functions. The monoidal category (C, ⊗, I) will thus henceforth be (C, ⊗, ½).

Recall that Turing's definition of his machines can be recast [START_REF] Pavlovic | Testing semantics: Connecting processes and process logics[END_REF]Appendix] to processes in the form

Q ρ ⊗ Σ ρ ⇀ Q ρ ⊗ Σ ⊗ Θ,
where -Q ρ is the finite set of states, always including the final state ∈ Q ρ ; -Σ is a fixed alphabet, always including the blank symbol ⊔ ∈ Σ; -Θ = {⊳, , ⊲} are the directions in which the head can move along the tape.

Let us recall the execution model: how these machines and processes compute. A Mealy machine

Q κ × I κ ⇀ Q κ × O inputs a string n ι -→ I,
where n = {0, 1, . . . , n -1} sequentially, e.g. it reads the inputs ι 0 , then ι 1 etc, and it outputs a string n ω -→ O in the same order, i.e. ω 0 , ω 1 , etc. In contrast, a Turing process in principle overwrites its inputs, and outputs the results of overwriting when it halts; therefore, in a Turing process, the input alphabet I and its output alphabet O must be the same, say I = O = Σ. Both the inputs, and the outputs, and the intermediary data of a Turing process are in the form w : Z -→ Σ, where all but finitely many values w(z) must be ⊔. So each word w : Z -→ Σ is still a finite string of symbols, like in the Mealy machine model. The difference is that w is written on the infinite 'tape', here represented by the set of integers Z, which allows the processing 'head' to move in both directions, or to stay stationary (while in a Mealy machine the head moves in the same direction at each step). We represent the position of the head by the integer 0, and the symbol that the head reads on that position is thus denoted by w(0). If the process

Q ρ ⊗ Σ ρ ⇀ Q ρ ⊗ Σ ⊗ Θ, which is a triple of functions ρ = ρ Q , ρ Σ , ρ Θ ,
is defined on a given state q ∈ Q ρ and a given input σ = w(0), then it will -overwrite σ with σ ′ = ρ Σ (q, σ), -transition to the state q ′ = ρ Q (q, σ), and -move the head to the next cell in the direction θ = ρ Θ (q, σ).

If q = , then ρ( , σ) = , σ, , which means that the process must halt at the state , if it ever reaches it. To capture this execution model formally, we extend Turing processes over the alphabet Σ, first to processes over the set Σ of Σ-words written on a tape, and then to computations with the inputs and the outputs from

Σ Qρ ⊗ Σ ρ ⇀ Qρ ⊗ Σ ⊗ Θ Qρ ⊗ Σ ρ ⇀ Qρ ⊗ Σ Qρ ⊗ Σ ρ ⇀ Σ
where Σ = w : Z -→ Σ | supp(w) < ∞ is the set of Σ-words written on a tape, and supp(w) = {z | w(z) = ⊔} . The elements of Σ are often also called the tape configurations. Writing the tuples in the form ρ = ρ Q , ρ Σ , define ρQ(q, w) = ρQ(q, w(0))

ρ Σ (q, w) = w ′ where w ′ (z) =      w(z -1) if ρΘ (q, w(0)) = ⊳ w(z) if ρΘ (q, w(0)) = w(z + 1) if ρΘ (q, w(0)) = ⊲      and
w(z) = ρΣ (q, w(0)) if z = 0 w(z) otherwise ρ(q, w) = w if q = ρ ρ(q, w) otherwise
The execution of all Turing processes can now be captured as a single process

Q ⊗ Σ p ⇀ Q ⊗ Σ,
where the state space Q is the disjoint union of the state spaces

Q ρ of all Turing processes ρ ∈ T , i.e. Q = ρ∈T Q ρ where T = {Q ρ ⊗ Σ ρ ⇀ Q ρ ⊗ Σ ⊗ Θ},
so that the elements of Q are the pairs ρ, q , where q ∈ Q ρ , and

Q ⊗ Σ p ⇀ Q ⊗ Σ is the pair p = p Q , p Σ
which, when applied to ρ, q ∈ Q and w ∈ Σ, gives p ρ, q , w = ρ, q ′ , w ′ where q ′ = ρ Q (q, w) and w ′ = ρ Σ (q, w). By applying Thm. 9 to the process Q ⊗ Σ p ⇀ Q ⊗ Σ, we get the following Proposition 10. There is an adaptive program P ∈ C • (Q, P) such that P (ρ, q) executes any Turing process ρ starting from the initial state q ∈ Q ρ . This means that for every tape configuration w ∈ Σ holds {| P (ρ, q)|} P w = P (ρ, q ′ ) and {| P (ρ, q)|} Σ w = w ′ , where q ′ = ρ Q q, w(0) is the next state of ρ, and w ′ = ρ Σ q, w is the next tape configuration. (The string diagram is the same as the one in Def. 8.) Corollary 1. The monoidal computer C is Turing complete.

Complexity

Evaluating Turing processes

Using the process Q⊗ Σ p ⇀ Q⊗ Σ, which according to Prop. 10 executes the single step transitions of Turing processes, we would now like to define a computation Q ⊗ Σ p ⇀ Σ that will evaluate Turing processes all the way; i.e. should execute all transitions that a process executes, and halt and deliver the output if the process halts, or diverge if the process diverges. The idea is to run something like the following pseudocode p ρ, q , w = x := ρ, q ; y := w;

(3) while pQ(x, y) =

x := pQ(x, y); y := p Σ (x, y) ; print y

We implement this program using the Fundamental Theorem of Computability. The function p is derived as a Kleene's fixed program for an intermediary function p, lifting the derivation from Sec. 5, as follows

Q ⊗ Σ p ⇀ Q ⊗ Σ P ⊗ Q ⊗ Σ p ⇀ Σ Q ⊗ Σ p ⇀ Σ
where p Υ, ρ, q , w =

         w if ρQ (q, w(0)) = {Υ } ρ, q ′ , w ′
otherwise where q ′ = ρQ q, w(0) and w ′ = p Σ ρ, q , w Using the if-branching from Sec. 3.1, this schema can be expressed in a monoidal computer, as illustrated in the following figure

{} ¬ ? if = {} p P Q Σ Σ Σ Q P Σ Σ P p = Σ {} P Σ Q P p = Σ {} Σ Q P [ ] P (4)
The first equation is obtained by setting Υ to be Kleene's fixed program P of p, and defining p = { P }. Given ρ, q ∈ Q and w ∈ Σ, this p thus runs ρ on w, starting from q and halting at , at which point it outputs the current w. If it does not reach , then ρ runs forever. The second equation proves the following proposition.

Proposition 11. There is an adaptive program P ∈ C • (Q, P) that evaluates any Turing process ρ starting from a given initial state q ∈ Q ρ . This means that for every tape configuration w ∈ Σ holds P (ρ, q) w = ρ(q, w).

Counting time

To count the steps in the executions of Turing processes, we add a counter i ∈ N to the Turing process evaluator p. The counter gets increased by 1 at each execution step, and thus counts them. We call t the computation which outputs the final count. If p halts, then t outputs the value of the counter i; if p does not halt, then t diverges as well. The pseudocode for t could thus look something like this: t ρ, q , w = x := ρ, q ; y := w; i := 0;

(5) while pQ(x, y) =

x := pQ(x, y); y := p Σ (x, y); i := i + 1 ;

print i

The implementation of t in a monoidal computer is similar to the implementation of p. It follows a similar derivation pattern:

Q ⊗ Σ p ⇀ Q ⊗ Σ P ⊗ Q ⊗ Σ ⊗ N t ⇀ N Q ⊗ Σ t ⇀ N
where t Υ, ρ, q , w, i = i if ρQ (q, w(0)) = {Υ } ρ, q ′ , w ′ , i + 1 otherwise with q ′ = ρ Q q, w(0) and w ′ = p Σ ρ, q , w . Like before, we set t ρ, q , w = T ρ, q , w, 0 , where and T is a Kleene fixed program of t. It is easy to see, and prove, that t ρ, q , w halts if and only if ρ(q, w) halts, and if it does halt, then it outputs the number of steps that ρ made before halting, having started from q and w. The string diagrams that implement t, T , t and T are similar to those in figure (4): just rename ps to ts and P s to T s, and add a string of type N on the right, with the successor operation on it, to increase the counter at each run. The added string outputs the time complexity t. Hence Proposition 12. There is an adaptive program T ∈ C • (Q, P) that outputs the number of steps that a Turing process ρ makes in any run from a given initial state q ∈ Q ρ to the halting state . If the Turing process ρ starting from q diverges, then the computation {T (ρ, q)} diverges as well. This means that, for every tape configuration w ∈ Σ holds T (ρ, q) w = t ρ, q , w .

Counting space

So far, we used the integers Z as the index set for the tape configurations w : Z -→ Σ. The position of the head has always been 0 ∈ Z, and whenever the head moves, the tape configuration w gets updated to w ′ = ρ Σ (q, w), where w ′ (0) is the new position of the head, and the rest of the word w is reindexed accordingly, as described in Sec. 5. At each point of the computation w thus describes the tape content relative to the current position of the head ; there is no record of the prior positions or contents. To count the tape cells used by Turing processes, we must make the tape itself into a first class citizen. The simplest way to do this seems to be to add a counter m ∈ Z, which denotes the offset of the current position of the head with respect to the initial position. This allows us to record how far up and down the tape, how far from its original position, does the head ever travel in either direction during the computation. To record these maximal offsets of the head, we need two more counters: let r ∈ Z be the highest value that the head offset m ever takes; and let ℓ ∈ Z be the lowest value that the head offset m ever takes. The number of cells that the head has visited during the computation is then clearly rℓ. To implement this space counting idea, we need to run a program roughly like this: s ρ, q , w = x := ρ, q ; y := w; ℓ, m, r := 0; [START_REF] Bernstein | Quantum complexity theory[END_REF] while pQ(x, y) =

x := pQ(x, y); y := p Σ (x, y);

if ρΘ q, w(0) = ⊳ if (m = ℓ){ℓ := ℓ -1}; m := m -1 if ρΘ q, w(0) = ⊲ if (m = r){r := r + 1}; m := m + 1 print r -ℓ
The derivation now becomes

Q ⊗ Σ p ⇀ Q ⊗ Σ P ⊗ Q ⊗ Σ ⊗ Z 3 s ⇀ N Q ⊗ Σ s ⇀ N where s Υ, ρ, q , w, ℓ, m, r =      r -ℓ if ρQ (q, w(0)) = {Υ } ρ, q ′ , . . . . . . w ′ , ℓ ′ , m ′ , r ′ otherwise
and where

q ′ = ρQ q, w(0) ℓ ′ = ℓ -1 if m = ℓ and ρΘ q, w(0) = ⊳ ℓ otherwise w ′ = p Σ ρ, q , w m ′ =      m -1 if ρΘ q, w(0) = ⊳ m if ρΘ q, w(0) = m + 1 if ρΘ q, w(0) = ⊲ r ′ = r + 1 if m = r and ρΘ q, w(0) = ⊲ r otherwise
Kleene's fixed point S of s defines s ρ, q , w = S ρ, q , w, 0, 0, 0 . The construction is summarized in the following figure:

{} ¬ ? if = {} p P Q N Q P N S s = N {} P Q S s = N {} Q S [ ] S 0 Σ Σ Σ Σ 0 - () ′ Z 3 Z 3 Z 3 ℓ ′ r ′ m ′ ℓ r r-ℓ (7)
The box () ′ , which computes ℓ ′ , m ′ and r ′ in figure [START_REF] Blum | A machine-independent theory of the complexity of recursive functions[END_REF], is implemented by composing several branching commands, e.g. as described at the end of Sec. 3.1. Implementing this box is an easy but instructive exercise in programming monoidal computers. Together, these constructions prove the following proposition.

Proposition 13. There is an adaptive program S ∈ C • (Q, P) that outputs the number of cells that a Turing process ρ uses in any run from a given initial state q ∈ Q ρ to the halting state . If the Turing process ρ starting from q diverges, then the computation {S(ρ, q)} diverges as well. This means that, for every tape configuration w ∈ Σ holds S(ρ, q) w = s ρ, q , w .

Remark. There are many variations of the above definitions in the literature, and several different counting conventions. E.g., an alternative to the above definition of s would be something like s ′ ρ, q , w = S ρ, q , w, w ℓ , 0, wr where

w ℓ = min{i ∈ Z | w(i) = ⊔} wr = max{i ∈ Z | w(i) = ⊔}
In contrast with s, where the space counting convention is that a memory cell counts as used if and only if it is ever reached by the head, the space counting convention behind s ′ is that every computation uses at least |w| = w rw ℓ cells, on which its initial input is written. If a Turing process halts without reading all of its input w, or even without reading any of it, the space used will still be |w|. Some textbooks adhere to the s-counting convention, some to the s ′ -counting convention, but many do not describe the process in enough detail to discern this difference. This is perhaps justified by the fact that the resulting complexity classes and their hierarchies are the same for all such subtly different counting conventions. E.g., the difference between s and s ′ is absorbed by the O-notation, and only arises for computations that do not read their inputs.

Final comments

A bird's eye view of algebra and coalgebra in computer science suggests that algebra provides denotational semantics of computation, whereas coalgebra provides operational semantics [START_REF] Klin | Bialgebras for structural operational semantics[END_REF][START_REF] Pavlovic | Testing semantics: Connecting processes and process logics[END_REF][START_REF] Turi | Towards a mathematical operational semantics[END_REF]. Denotational semantics goes beyond the purely extensional view of computations (as maps from inputs to outputs), and models certain computational effects (such as non-termination, exceptions, nondeterminism, etc.). Operational semantics goes further, and models computational operations. While computational effects are thus presented using the suitable algebraic operations in denotational semantics, computational behaviors are represented as elements of final coalgebras in operational semantics. But although both the denotational and the operational approaches go beyond the purely extensional view, neither has supported a genuinely intensional view, envisioned by Turing and von Neumann, where programs are data. Therefore, in spite of the tremendous successes in understanding and systematizing computational structures and behaviors, categorical semantics of computation has remained largely disjoint from theories of computability and complexity. The claim put forward in this paper is that coalgebra provides a natural categorical framework for a fully intensional categorical theory of computability and complexity. The crucial step that enables this theory leads beyond final coalgebras, that assign unique descriptions to computational behaviors of fixed types, to universal coalgebras, that assign non-unique descriptions to computations of arbitrary types. These descriptions are what we usually call programs. Our message is thus that programmability is a coalgebraic property, just like computational behaviors are coalgebraic. This message is formally expressed through universal processes; it can perhaps be expressed more generally through universal coalgebras, as families of weakly final coalgebras, all carried by the same universal state space. Thm. 9 spells out in the framework of monoidal computer the fact that every Turing complete programming language provides a universal coalgebra for computable functions of all types; and vice versa, every universal coalgebra induces a corresponding notion of program. Just like abstract computational behaviors of a given type are precisely the elements of a final coalgebra of that type, abstract programs are precisely the elements of a universal coalgebra. Just like final coalgebras can be used to define semantics of computational behaviors [START_REF] Pavlovic | Testing semantics: Connecting processes and process logics[END_REF], universal coalgebras can be used to define semantics of programs. From a slightly different angle, the fact that universal coalgebras characterize monoidal computers, proven in Thm. 9, can also be viewed as a coalgebraic characterization of computability. There are, of course, many characterizations of computability. The upshot of this one is, however, in Propositions 12 and 13: the coalgebaic view of computability opens an alley towards complexity. In any universe of computable functions, normal complexity measures [START_REF] Pavlovic | Monoidal computer II: Normal complexity by string diagrams[END_REF] can be programmed coalgebraically. Combining this coalgebraic view of complexity with the algebraic view of randomized computation seems to open up a path towards a categorical model of one-way functions, and towards categorical cryptography, which has been the original goal of this project [START_REF] Pavlovic | Gaming security by obscurity[END_REF].

  where 1 is the final object of C, and all morphisms of C are comonoid homomorphisms, or equivalently, the families A ∆ -→ A × A and A ⊤ -→ 1 are natural. Cartesian categories are thus just monoidal categories with natural families of copying and deleting operations. Definition 1. A data service of type A in a monoidal category C is a comonoid structure A ⊗ A ∆ ← -A ⊤ -→ I, where ∆ provides the copying service, and ⊤ provides the deleting service. Definition 2. A morphism f ∈ C(

Definition 3 .

 3 A monoidal computer is a (strict) symmetric monoidal category C, with a data service A ⊗ A ∆ ← -A ⊤ -→ I on every A, and a distinguished type of programs P, given with, for every pair of types A, B, an X-natural family of surjections C • (X, P) C(X ⊗ A, B) γ AB X , representing program evaluations.

Proposition 4 .

 4 Let C be a symmetric monoidal category with data services. Then specifying the program evaluations γ AB X : C • (X, P) ։ C(X ⊗ A, B) that make C into a monoidal computer, as defined in Def. 3, is equivalent to specifying for any three types A, B, C ∈ |C| the following two morphisms:(a) a universal evaluator {} AB ∈ C(PA, B) such that for every computation

3. 3

 3 Encoding all types Proposition 5. Every type B in a monoidal computer is a retract of the type of programs P. More precisely, for every type B ∈ |C| there are computations e B : B P : d B such that e B is a map, and e B ; d B = id B . We often call e B the encoding of B and d B ∈ C(P, B) is the corresponding decoding.

Theorem 6 .

 6 In every monoidal computer C, every computation g ∈ C(P⊗A, B) has a Kleene fixed point, i.e. a program Γ ∈ C(P) such that g(Γ, a) = {Γ } a.

Theorem 9 .

 9 We denote the category of AB-processes by C AB . Definition 8. A universal process in a monoidal category C is carried by a universal state space S ∈ |C|, which comes with a weakly final AB-process SA {| |} --→ SB for every pair A, B ∈ |C|. The weak finality means that for every p ∈ C(X ⊗ A, X ⊗ B) there is an X-adaptive program P ∈ C • (X, S) where {|P (x)|} S a = P (pX (x, a)) {|P (x)|} B a = pB (x, a) Let C be a symmetric monoidal category with data services. Then C is a monoidal computer if and only if it has a universal process. The type P of programs coincides with the universal state space S. Proof. Given a weakly final AB-process S ⊗ A {| |} --→ S ⊗ B, we show that

  The X-adaptive program P ∈ C • (P) corresponding to the process p ∈ C(XA, XB)is now P (x) = P , x XBP .

  ABX if and only if the model is essentially extensional (i.e., it contains an extensional retract). We will see in Sec. 3.1 that the program evaluation γ AB

). Could we get away with less? No, because the program evaluation γ AB X has a left inverse λ X is in fact executed by a universal evaluator {} AB ∈ C(P ⊗ A, B), and thus takes the form γ AB X

The course materials are available from http://www.asecolab.org/courses/222/, and the textbook[START_REF] Pavlovic | Basic Concepts of Computer Science (with Pictures)[END_REF] is in preparation.

Both Turing and von Neumann devoted a lot of attention to studying life as a computational process. Their ideas have been adopted in biology[START_REF] Barbieri | Code Biology: A New Science of Life[END_REF], but most computer scientists remain skeptical.