TSG-19861: Support client hello fragmentv3.0.5

3 files changed, 564 insertions, 14 deletions

diff --git a/src/SSL_Analyze.h b/src/SSL_Analyze.h
index b8dabac..a58f024 100644
--- a/src/SSL_Analyze.h
+++ b/src/SSL_Analyze.h
@@ -3,6 +3,7 @@
 #include <MESA/stream.h>
 
 #include "ssl.h"
+#include "SSL_Message.h"
 
 #if(__GNUC__ * 100 + __GNUC_MINOR__ * 10 + __GNUC_PATCHLEVEL__ >= 410)
 #define atomic_inc(x) __sync_add_and_fetch((x),1)
@@ -62,6 +63,8 @@ struct ssl_business_info
 
 struct ssl_record_trunk
 {
+	unsigned char is_offset_header;
+	struct ssl_record_header header;
 	int cache_len;
 	char* cache_buff;
 };
diff --git a/src/SSL_Message.c b/src/SSL_Message.c
index d3bff89..bbc9033 100644
--- a/src/SSL_Message.c
+++ b/src/SSL_Message.c
@@ -2,6 +2,8 @@
 #include <string.h>
 #include <stdlib.h>
 
+#include "utstring.h"
+
 #include "SSL_Analyze.h"
 #include "ssl.h"
 #include "SSL_Message.h"
@@ -25,6 +27,12 @@
 #define ENCRPTED_SERVER_NAME_EXT_TYPE	0xFFCE
 #define ENCRPTED_CLIENT_HELLO_EXT_TYPE	0xFE0D
 
+#define	EC_POINT_FORMATS_EXT_TYPE		0x000B
+
+// https://datatracker.ietf.org/doc/html/rfc7919
+// Supported Groups
+#define SUPPORTED_GROUPS_EXT_TYPE		0x000A
+
 #define CERTIFICATE_HDRLEN		7
 #define SSL_CERTIFICATE_HDRLEN  3
 
@@ -48,6 +56,22 @@ const struct ssl_value2string ssl_version_list[] =
     { UNKNOWN_VERSION, 		NULL }
 };
 
+// https://tools.ietf.org/html/draft-davidben-tls-grease-00
+static int ssl_is_grease_value(unsigned short val)
+{
+	if ((val & 0x0f)!=0x0a)
+	{
+		return 0;
+	}
+
+	if((val & 0xff) != ((val >> 8) & 0xff))
+	{
+		return 0;
+	}
+
+	return 1;
+}
+
 const char *ssl_get_suite(struct ssl_l2v *ciphersuites)
 {
 	if (ciphersuites == NULL)
@@ -127,7 +151,7 @@ void ssl_trunk_free(struct ssl_runtime_context *ssl_context, int thread_seq)
 			ssl_context->record.cache_buff=NULL;
 		}
 		
-		ssl_context->record.cache_len=0;
+		memset(&(ssl_context->record), 0, sizeof(struct ssl_record_trunk));
 	}
 }
 
@@ -310,6 +334,17 @@ int ssl_parse_encrypt_server_name(struct ssl_client_hello *chello, struct ssl_l2
 int ssl_parse_client_hello(struct ssl_client_hello *chello, unsigned char *payload, int payload_len)
 {
 	int offset=0,one_ltv=0;
+	unsigned int ec_point_format=0;
+
+	UT_string *ja3_string,*cipher_suite_string,*ec_string,*ex_string;
+	utstring_new(ja3_string);
+	utstring_new(cipher_suite_string);
+	utstring_printf(cipher_suite_string, ",");
+	utstring_new(ec_string);
+	utstring_printf(ec_string, ",");
+	utstring_new(ex_string);
+	utstring_printf(ex_string, ",");
+
 	chello->total_len=BtoL3BytesNum((const char *)(payload+1));
 	if(chello->total_len<0) /*CLIENT_HELLO_HDRLEN: 4 means client_type+len*/
 	{
@@ -318,7 +353,7 @@ int ssl_parse_client_hello(struct ssl_client_hello *chello, unsigned char *paylo
 
 	if((chello->total_len+CLIENT_HELLO_HDRLEN > payload_len) || (chello->total_len-(int)sizeof(chello->version)<0))
 	{
-		return SSL_FLASE;
+		return SSL_CONTINUE;
 	}
 
 	chello->version=ssl_get_hello_version((unsigned char *)payload, payload_len);
@@ -327,6 +362,7 @@ int ssl_parse_client_hello(struct ssl_client_hello *chello, unsigned char *paylo
 		return SSL_FLASE;
 	}
 
+	utstring_printf(ja3_string, "%u", chello->version);
 	offset+=(CLIENT_HELLO_HDRLEN+sizeof(chello->version));
 
 	/*get client hello random*/
@@ -356,6 +392,19 @@ int ssl_parse_client_hello(struct ssl_client_hello *chello, unsigned char *paylo
 	{
 		return SSL_FLASE;
 	}
+
+	if(chello->ciphersuites.len>0)
+	{
+		for(unsigned short i=0; i<chello->ciphersuites.len; i+=2)
+		{
+			unsigned short cipher_suite=BtoL2BytesNum((const char *)(chello->ciphersuites.value+i));
+			if(ssl_is_grease_value(cipher_suite)==0)
+			{
+				utstring_printf(cipher_suite_string, "%u-", cipher_suite);
+			}
+		}
+	}
+
 	offset+=one_ltv;
 
 	/*get client hello compress*/
@@ -380,6 +429,12 @@ int ssl_parse_client_hello(struct ssl_client_hello *chello, unsigned char *paylo
 			{
 				return SSL_FLASE;
 			}
+
+			if(ssl_is_grease_value(chello->extensions.extension[ex_offset].type)==0)
+			{
+				utstring_printf(ex_string, "%u-", chello->extensions.extension[ex_offset].type);
+			}
+
 			offset+=one_ltv;
 
 			switch(chello->extensions.extension[ex_offset].type)
@@ -399,6 +454,44 @@ int ssl_parse_client_hello(struct ssl_client_hello *chello, unsigned char *paylo
 				case	ALPN_EXT_TYPE:
 					chello->alpn=&(chello->extensions.extension[ex_offset++]);
 					break;
+				case	EC_POINT_FORMATS_EXT_TYPE:
+					// parse ec point formats
+					{
+						char length=BtoL1BytesNum((const char*)(chello->extensions.extension[ex_offset].value));
+						switch(length)
+						{
+							case	1:
+								ec_point_format=BtoL1BytesNum((const char*)(chello->extensions.extension[ex_offset].value+1));
+								break;
+							case	2:
+								ec_point_format=BtoL2BytesNum((const char*)(chello->extensions.extension[ex_offset].value+1));
+								break;
+							case	3:
+								ec_point_format=BtoL3BytesNum((const char*)(chello->extensions.extension[ex_offset].value+1));
+								break;
+							case	4:
+								ec_point_format=BtoL4BytesNum((const char*)(chello->extensions.extension[ex_offset].value+1));
+								break;
+							default:
+								ec_point_format=0;
+								break;
+						}
+					}
+					break;
+				case	SUPPORTED_GROUPS_EXT_TYPE:
+					// parse supported groups
+					{
+						unsigned short length=BtoL2BytesNum((const char*)(chello->extensions.extension[ex_offset].value));
+						for(unsigned short j=0; j<length; j+=2)
+						{
+							unsigned short group=BtoL2BytesNum((const char*)(chello->extensions.extension[ex_offset].value+j+2));
+							if(ssl_is_grease_value(group)==0)
+							{
+								utstring_printf(ec_string, "%u-", group);
+							}
+						}
+					}
+					break;
 				default:
 					break;
 			}
@@ -406,6 +499,20 @@ int ssl_parse_client_hello(struct ssl_client_hello *chello, unsigned char *paylo
 
 		chello->extensions.num=ex_offset;
 	}
+
+	utstring_bincpy(ja3_string, utstring_body(cipher_suite_string), (utstring_len(cipher_suite_string)==1 ? utstring_len(cipher_suite_string) : utstring_len(cipher_suite_string)-1));
+	utstring_bincpy(ja3_string, utstring_body(ex_string), (utstring_len(ex_string)==1 ? utstring_len(ex_string) : utstring_len(ex_string)-1));
+	utstring_bincpy(ja3_string, utstring_body(ec_string), (utstring_len(ec_string)==1 ? utstring_len(ec_string) : utstring_len(ec_string)-1));
+	utstring_printf(ja3_string, ",%u", ec_point_format);
+
+	chello->ja3.md5_len=ja3_md5sum(utstring_body(ja3_string), utstring_len(ja3_string), chello->ja3.md5, sizeof(chello->ja3.md5));
+	chello->ja3.md5[chello->ja3.md5_len]='\0';
+
+	utstring_free(ja3_string);
+	utstring_free(cipher_suite_string);
+	utstring_free(ec_string);
+	utstring_free(ex_string);
+
 	return SSL_TRUE;
 }
 
@@ -731,7 +838,7 @@ int ssl_parse_handshake(const struct streaminfo *a_tcp, struct ssl_runtime_conte
 		}
 	}
 
-	return SSL_TRUE;;
+	return SSL_TRUE;
 }
 
 int ssl_parse_application_data(const struct streaminfo *a_tcp, struct ssl_runtime_context *ssl_context, char *payload, int payload_len, int thread_seq, const void *a_packet)
@@ -864,18 +971,28 @@ int ssl_parse_message(const struct streaminfo *a_tcp, struct ssl_runtime_context
 
 	while(payload_len-offset > SSL_RECORD_HDRLEN)
 	{
-		struct ssl_record_header *ssl_record=(struct ssl_record_header *)(payload+offset);
+		int one_record_len=0;
+		struct ssl_record_header *ssl_record=NULL;
 		
-		int one_record_len=htons(ssl_record->total_len);
-		ssl_context->is_ssl_stream=SSL_TRUE;
-		
-		if((payload_len-offset) < one_record_len)
+		if(ssl_context->record.is_offset_header==1)
 		{
-			ssl_trunk_cache(ssl_context, payload+offset, payload_len-offset, thread_seq);
-			break; //cache
+			ssl_record=&(ssl_context->record.header);
+			one_record_len=payload_len;
+		}
+		else
+		{
+			ssl_record=(struct ssl_record_header *)(payload+offset);
+			one_record_len=htons(ssl_record->total_len);
+			ssl_context->is_ssl_stream=SSL_TRUE;
+			
+			if((payload_len-offset) < one_record_len)
+			{
+				ssl_trunk_cache(ssl_context, payload+offset, payload_len-offset, thread_seq);
+				break; //cache
+			}
+			
+			offset+=SSL_RECORD_HDRLEN;
 		}
-		
-		offset+=SSL_RECORD_HDRLEN;
 		
 		switch (ssl_record->content_type)
 		{
@@ -907,6 +1024,14 @@ int ssl_parse_message(const struct streaminfo *a_tcp, struct ssl_runtime_context
 			break;
 		}
 
+		if(state==SSL_CONTINUE)
+		{
+			ssl_context->record.is_offset_header=1;
+			ssl_context->record.header=*ssl_record;
+			ssl_trunk_cache(ssl_context, payload+offset, payload_len-offset, thread_seq);
+			break;
+		}
+		
 		offset+=one_record_len;
 	}
 
@@ -941,8 +1066,23 @@ int ssl_parse_stream(const struct streaminfo *a_tcp, struct ssl_runtime_context
 	if(ssl_context->record.cache_len>0)
 	{
 		payload_len=MIN((int)tcp_detail->datalen, (g_ssl_runtime_para.max_cache_len - ssl_context->record.cache_len));
-		memcpy(ssl_context->record.cache_buff + ssl_context->record.cache_len, tcp_detail->pdata, payload_len);
-		ssl_context->record.cache_len += payload_len;
+		if(ssl_context->record.is_offset_header==1)
+		{
+			if(payload_len<=SSL_RECORD_HDRLEN)
+			{
+				ssl_trunk_free(ssl_context, thread_seq);
+				return SSL_TRUE;
+			}
+
+			memcpy(ssl_context->record.cache_buff + ssl_context->record.cache_len, ((char *)(tcp_detail->pdata))+SSL_RECORD_HDRLEN, payload_len-SSL_RECORD_HDRLEN);
+			ssl_context->record.cache_len += payload_len-SSL_RECORD_HDRLEN;
+		}
+		else
+		{
+			memcpy(ssl_context->record.cache_buff + ssl_context->record.cache_len, tcp_detail->pdata, payload_len);
+			ssl_context->record.cache_len += payload_len;
+		}
+		
 		payload_len=ssl_context->record.cache_len;
 		payload=ssl_context->record.cache_buff;
 	}
diff --git a/src/utstring.h b/src/utstring.h
new file mode 100644
index 0000000..4cf5ffd
--- /dev/null
+++ b/src/utstring.h
@@ -0,0 +1,407 @@
+/*
+Copyright (c) 2008-2018, Troy D. Hanson   http://troydhanson.github.com/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* a dynamic string implementation using macros
+ */
+#ifndef UTSTRING_H
+#define UTSTRING_H
+
+#define UTSTRING_VERSION 2.1.0
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdarg.h>
+
+#ifdef __GNUC__
+#define UTSTRING_UNUSED __attribute__((__unused__))
+#else
+#define UTSTRING_UNUSED
+#endif
+
+#ifdef oom
+#error "The name of macro 'oom' has been changed to 'utstring_oom'. Please update your code."
+#define utstring_oom() oom()
+#endif
+
+#ifndef utstring_oom
+#define utstring_oom() exit(-1)
+#endif
+
+typedef struct {
+    char *d;  /* pointer to allocated buffer */
+    size_t n; /* allocated capacity */
+    size_t i; /* index of first unused byte */
+} UT_string;
+
+#define utstring_reserve(s,amt)                            \
+do {                                                       \
+  if (((s)->n - (s)->i) < (size_t)(amt)) {                 \
+    char *utstring_tmp = (char*)realloc(                   \
+      (s)->d, (s)->n + (amt));                             \
+    if (!utstring_tmp) {                                   \
+      utstring_oom();                                      \
+    }                                                      \
+    (s)->d = utstring_tmp;                                 \
+    (s)->n += (amt);                                       \
+  }                                                        \
+} while(0)
+
+#define utstring_init(s)                                   \
+do {                                                       \
+  (s)->n = 0; (s)->i = 0; (s)->d = NULL;                   \
+  utstring_reserve(s,100);                                 \
+  (s)->d[0] = '\0';                                        \
+} while(0)
+
+#define utstring_done(s)                                   \
+do {                                                       \
+  if ((s)->d != NULL) free((s)->d);                        \
+  (s)->n = 0;                                              \
+} while(0)
+
+#define utstring_free(s)                                   \
+do {                                                       \
+  utstring_done(s);                                        \
+  free(s);                                                 \
+} while(0)
+
+#define utstring_new(s)                                    \
+do {                                                       \
+  (s) = (UT_string*)malloc(sizeof(UT_string));             \
+  if (!(s)) {                                              \
+    utstring_oom();                                        \
+  }                                                        \
+  utstring_init(s);                                        \
+} while(0)
+
+#define utstring_renew(s)                                  \
+do {                                                       \
+   if (s) {                                                \
+     utstring_clear(s);                                    \
+   } else {                                                \
+     utstring_new(s);                                      \
+   }                                                       \
+} while(0)
+
+#define utstring_clear(s)                                  \
+do {                                                       \
+  (s)->i = 0;                                              \
+  (s)->d[0] = '\0';                                        \
+} while(0)
+
+#define utstring_bincpy(s,b,l)                             \
+do {                                                       \
+  utstring_reserve((s),(l)+1);                             \
+  if (l) memcpy(&(s)->d[(s)->i], b, l);                    \
+  (s)->i += (l);                                           \
+  (s)->d[(s)->i]='\0';                                     \
+} while(0)
+
+#define utstring_concat(dst,src)                                 \
+do {                                                             \
+  utstring_reserve((dst),((src)->i)+1);                          \
+  if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \
+  (dst)->i += (src)->i;                                          \
+  (dst)->d[(dst)->i]='\0';                                       \
+} while(0)
+
+#define utstring_len(s) ((s)->i)
+
+#define utstring_body(s) ((s)->d)
+
+UTSTRING_UNUSED static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {
+   int n;
+   va_list cp;
+   for (;;) {
+#ifdef _WIN32
+      cp = ap;
+#else
+      va_copy(cp, ap);
+#endif
+      n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);
+      va_end(cp);
+
+      if ((n > -1) && ((size_t) n < (s->n-s->i))) {
+        s->i += n;
+        return;
+      }
+
+      /* Else try again with more space. */
+      if (n > -1) utstring_reserve(s,n+1); /* exact */
+      else utstring_reserve(s,(s->n)*2);   /* 2x */
+   }
+}
+#ifdef __GNUC__
+/* support printf format checking (2=the format string, 3=start of varargs) */
+static void utstring_printf(UT_string *s, const char *fmt, ...)
+  __attribute__ (( format( printf, 2, 3) ));
+#endif
+UTSTRING_UNUSED static void utstring_printf(UT_string *s, const char *fmt, ...) {
+   va_list ap;
+   va_start(ap,fmt);
+   utstring_printf_va(s,fmt,ap);
+   va_end(ap);
+}
+
+/*******************************************************************************
+ * begin substring search functions                                            *
+ ******************************************************************************/
+/* Build KMP table from left to right. */
+UTSTRING_UNUSED static void _utstring_BuildTable(
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+
+    i = 0;
+    j = i - 1;
+    P_KMP_Table[i] = j;
+    while (i < (long) P_NeedleLen)
+    {
+        while ( (j > -1) && (P_Needle[i] != P_Needle[j]) )
+        {
+           j = P_KMP_Table[j];
+        }
+        i++;
+        j++;
+        if (i < (long) P_NeedleLen)
+        {
+            if (P_Needle[i] == P_Needle[j])
+            {
+                P_KMP_Table[i] = P_KMP_Table[j];
+            }
+            else
+            {
+                P_KMP_Table[i] = j;
+            }
+        }
+        else
+        {
+            P_KMP_Table[i] = j;
+        }
+    }
+
+    return;
+}
+
+
+/* Build KMP table from right to left. */
+UTSTRING_UNUSED static void _utstring_BuildTableR(
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+
+    i = P_NeedleLen - 1;
+    j = i + 1;
+    P_KMP_Table[i + 1] = j;
+    while (i >= 0)
+    {
+        while ( (j < (long) P_NeedleLen) && (P_Needle[i] != P_Needle[j]) )
+        {
+           j = P_KMP_Table[j + 1];
+        }
+        i--;
+        j--;
+        if (i >= 0)
+        {
+            if (P_Needle[i] == P_Needle[j])
+            {
+                P_KMP_Table[i + 1] = P_KMP_Table[j + 1];
+            }
+            else
+            {
+                P_KMP_Table[i + 1] = j;
+            }
+        }
+        else
+        {
+            P_KMP_Table[i + 1] = j;
+        }
+    }
+
+    return;
+}
+
+
+/* Search data from left to right. ( Multiple search mode. ) */
+UTSTRING_UNUSED static long _utstring_find(
+    const char *P_Haystack,
+    size_t P_HaystackLen,
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+    long V_FindPosition = -1;
+
+    /* Search from left to right. */
+    i = j = 0;
+    while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) )
+    {
+        while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) )
+        {
+            i = P_KMP_Table[i];
+        }
+        i++;
+        j++;
+        if (i >= (int)P_NeedleLen)
+        {
+            /* Found. */
+            V_FindPosition = j - i;
+            break;
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from right to left. ( Multiple search mode. ) */
+UTSTRING_UNUSED static long _utstring_findR(
+    const char *P_Haystack,
+    size_t P_HaystackLen,
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+    long V_FindPosition = -1;
+
+    /* Search from right to left. */
+    j = (P_HaystackLen - 1);
+    i = (P_NeedleLen - 1);
+    while ( (j >= 0) && (j >= i) )
+    {
+        while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) )
+        {
+            i = P_KMP_Table[i + 1];
+        }
+        i--;
+        j--;
+        if (i < 0)
+        {
+            /* Found. */
+            V_FindPosition = j + 1;
+            break;
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from left to right. ( One time search mode. ) */
+UTSTRING_UNUSED static long utstring_find(
+    UT_string *s,
+    long P_StartPosition,   /* Start from 0. -1 means last position. */
+    const char *P_Needle,
+    size_t P_NeedleLen)
+{
+    long V_StartPosition;
+    long V_HaystackLen;
+    long *V_KMP_Table;
+    long V_FindPosition = -1;
+
+    if (P_StartPosition < 0)
+    {
+        V_StartPosition = s->i + P_StartPosition;
+    }
+    else
+    {
+        V_StartPosition = P_StartPosition;
+    }
+    V_HaystackLen = s->i - V_StartPosition;
+    if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) )
+    {
+        V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
+        if (V_KMP_Table != NULL)
+        {
+            _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table);
+
+            V_FindPosition = _utstring_find(s->d + V_StartPosition,
+                                            V_HaystackLen,
+                                            P_Needle,
+                                            P_NeedleLen,
+                                            V_KMP_Table);
+            if (V_FindPosition >= 0)
+            {
+                V_FindPosition += V_StartPosition;
+            }
+
+            free(V_KMP_Table);
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from right to left. ( One time search mode. ) */
+UTSTRING_UNUSED static long utstring_findR(
+    UT_string *s,
+    long P_StartPosition,   /* Start from 0. -1 means last position. */
+    const char *P_Needle,
+    size_t P_NeedleLen)
+{
+    long V_StartPosition;
+    long V_HaystackLen;
+    long *V_KMP_Table;
+    long V_FindPosition = -1;
+
+    if (P_StartPosition < 0)
+    {
+        V_StartPosition = s->i + P_StartPosition;
+    }
+    else
+    {
+        V_StartPosition = P_StartPosition;
+    }
+    V_HaystackLen = V_StartPosition + 1;
+    if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) )
+    {
+        V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
+        if (V_KMP_Table != NULL)
+        {
+            _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table);
+
+            V_FindPosition = _utstring_findR(s->d,
+                                             V_HaystackLen,
+                                             P_Needle,
+                                             P_NeedleLen,
+                                             V_KMP_Table);
+
+            free(V_KMP_Table);
+        }
+    }
+
+    return V_FindPosition;
+}
+/*******************************************************************************
+ * end substring search functions                                              *
+ ******************************************************************************/
+
+#endif /* UTSTRING_H */